[USACO2010 Hol Gold 【cowpol】](性质证明、LCA) Or (树的分治A7个点)

【题目链接】http://ace.delos.com/ioiupload?init=1&a=nejLCFTaRn6
或者八中：http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1776
不过八中由于是Windows，所以要手写栈~没事可以去写一写~
Pascal的话就不用怕了，直接开编译开关：{$M 10000000}
【题目大意】
n<=20 0000
树上的每个点都涂了一种颜色，
对于每种颜色，问属于这种颜色的点中的最远点对是多少?
边权全是1。
时限2s per data
【算法分析】
做法1：
一开始看比较直观的就是对树进行基于点的分治。
时间复杂度O(n lg n)。
空间复杂度O(n lg n)。
但是由于常数过大，终究逃脱不了TLE的命运。

做法2：
首先我们画出一棵树。
然后可以发现,无论怎么画，对于同一种颜色，最长路出现时，其中一个点必然是这颗树中深度最大的点。
下面给出我的证明：
设x,y,z为三个同颜色的点，x为所有该种颜色中的深度最大的一个点。
那么我们现在要证命题：dis(y,z)<=max(dis(x,y),dis(x,z))。

可以用这个图先直观地感受一下。
下面我们采用反证法。
题设：dis(y,z)>max(dis(x,y),dis(x,z))。
将这个不等式转化成一个不等式组：
dep[x]+dep[y]-dep[LCA(x,y)]*2dep[x]+dep[z]-dep[LCA(x,z)]*2dep[x]-dep[z]<(dep[LCA(x,y)]-dep[LCA(y,z)])*2  ————①
dep[x]-dep[y]<(dep[LCA(x,z)]-dep[LCA(y,z)])*2  ————② 我们对这个两个不等式进行放大，得：
dep[LCA(x,y)]-dep[LCA(y,z)]>0
dep[LCA(x,z)]-dep[LCA(y,z)]>0
（之所以可以这样做，是因为dep[x]>=dep[z] && dep[x]>=dep[y]）

下面进行分类讨论：
1、dep[LCA(x,y)]<=dep[LCA(y,z)]。那么①式显然不成立。矛盾。
2、dep[LCA(x,y)]>dep[LCA(y,z)]。那么z的位置有两种可能。
①z是y的子孙。这样显然与题设矛盾。因为dis(x,z)>=dis(y,z)。（x到z的路径包括了y到z的路径）
②LCA(y,z)在“LCA(x,y)到y”的路径上。那么在这种情况下，我们看②式。

显然，此时LCA(x,z)=LCA(y,z)，所以②式不可能成立。于是又与题设矛盾。
所以，综上所述，①②两式不可能同时成立。于是题设不可能成立。
于是反证出命题：dis(y,z)<=max(dis(x,y),dis(x,z)) 正确。 有这个了结论，那么就可以找出每种颜色里深度最大的。然后其它的点都和它算一下距离就可以了。这里面用到了最近公共祖先(LCA)的经典算法。
【时间复杂度】O(n)
【空间复杂度】O(n)
【其它】这个代码在衡阳八中A不了，因为会栈溢出。
【时间和空间状况】
> Run 1: OK [0.011 secs, 8600 KB]
> Run 2: OK [0.011 secs, 8600 KB]
> Run 3: OK [0.022 secs, 8600 KB]
> Run 4: OK [0.022 secs, 8600 KB]
> Run 5: OK [0.011 secs, 8600 KB]
> Run 6: OK [0.140 secs, 11636 KB]
> Run 7: OK [0.151 secs, 11372 KB]
> Run 8: OK [0.378 secs, 15116 KB]
> Run 9: OK [0.367 secs, 13972 KB]
> Run 10: OK [0.464 secs, 17840 KB]
> Run 11: OK [0.572 secs, 17924 KB]
> Run 12: OK [0.745 secs, 22880 KB]
> Run 13: OK [0.680 secs, 22620 KB]
【CODE】
/*
ID:jie22221
TASK:cowpol
LANG:C++
*/
#include #include #include #include #define clr(a) memset((a),(0),sizeof(a))
using namespace std;
const int maxn=200005;
struct edge{int y;edge *next;};
int n,k;
int ans[maxn],belong[maxn],d[maxn],mdp[maxn],f[maxn];
bool v[maxn];

struct Link_t{
edge *ls[maxn];
void add(int x,int y){
edge *t=(edge*)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}
}G,Q;

void init(){
clr(G.ls);
clr(Q.ls);
clr(d);
clr(mdp);
clr(v);
clr(ans);
scanf("%d%d",&n,&k);
for (int x,i=1;i<=n;i++){
scanf("%d%d",&belong[i],&x);
G.add(x,i);
G.add(i,x);
}
}

void dfs(int p,int fa){
for (edge *t=G.ls[p];t;t=t->next)
if (t->y!=fa){
d[t->y]=d[p]+1;
dfs(t->y,p);
}
}

void make_Q(){
for (int i=1;i<=n;i++)
if (!mdp[belong[i]] || d[i]>d[mdp[belong[i]]])
mdp[belong[i]]=i;
for (int i=1;i<=n;i++)
if (mdp[belong[i]]!=i){
Q.add(i,mdp[belong[i]]);
Q.add(mdp[belong[i]],i);
}
}

int gf(int p){
if (f[p]==p) return p;
return f[p]=gf(f[p]);
}

void solve(int p,int fa){
f[p]=p;
for (edge *t=G.ls[p];t;t=t->next)
if (t->y!=fa)
solve(t->y,p);
v[p]=true;
for (edge *t=Q.ls[p];t;t=t->next)
if (v[t->y])
ans[belong[p]]=max(ans[belong[p]],d[t->y]+d[p]-2*d[gf(t->y)]);
f[p]=fa;
}

int main(){
freopen("cowpol.in","r",stdin);
freopen("cowpol.out","w",stdout);
init();
dfs(1,0);
make_Q();
solve(1,0);
for (int i=1;i<=k;i++)
printf("%dn",ans[i]);
}