显然，对于一个党派，相距最远的两头牛中至少有一头是这个党派中深度最大的牛之一（这一点联系求树的直径，先随便从一点找最远，再从那儿找最远）。
所以每个党派的范围=max{最深的牛的深度+某头牛的深度-它们的最近公共祖先的深度*2,某头牛属于这个党派}。
问题的主要矛盾是LCA，然后，写了第一个Tarjan的LCA，由于数据太BT，要非递归，并且，即使这样下面的代码在Windows下无法编译（好像是因为开的内存太大了），但可以在USACO的测评系统下通过，所以在Linux下可以用的。
然后，LCA还有其它的算法可以做，有空再弄其它的，LCA这还是第一次写。
CODE:
/*
PROG: cowpol
LANG: C++
ID: boleyn.2
*/
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-6-4
DESCRIPTION:
TITLE: Cow Politics [Andre Kessler, 2009]
CONTENT:
Farmer John’s cows are living on N (2 <= N <= 200,000) different
pastures conveniently numbered 1..N. Exactly N-1 bidirectional cow
paths (of unit length) connect these pastures in various ways, and
each pasture is reachable from any other cow pasture by traversing
one or more of these paths (thus, the pastures and paths form a
graph called a tree).
The input for a particular set of pastures will specify the parent
node P_i (0 <= P_i <= N) for each pasture. The root node will specify
parent P_i == 0, which means it has no parent.
The cows have organized K (1 <= K <= N/2) different political parties
conveniently numbered 1..K. Each cow identifies with a single
political party; cow i identifies with political party A_i (1 <=
A_i <= K). Each political party includes at least two cows.
The political parties are feuding and would like to know how much
‘range’ each party covers. The range of a party is the largest
distance between any two cows within that party (over cow paths).
For example, suppose political party 1 consists of cows 1, 3, and
6, political party 2 consists of cows 2, 4, and 5, and the pastures
are connected as follows (party 1 members are marked as -n-):
-3-
|
-1-
/ | \
2 4 5
|
-6-
The greatest distance between any two pastures of political party
1 is 3 (between cows 3 and 6), and the greatest distance for political
party 2 is 2 (between cows 2 and 4, between cows 4 and 5, and between
cows 5 and 2).
Help the cows determine party ranges.
TIME LIMIT: 2 seconds
MEMORY LIMIT: 64MB
PROBLEM NAME: cowpol
INPUT FORMAT:
* Line 1: Two space-separated integers: N and K
* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i
and P_i
SAMPLE INPUT (file cowpol.in):
6 2
1 3
2 1
1 0
2 1
2 1
1 5
OUTPUT FORMAT:
* Lines 1..K: Line i contains a single integer that is the range of
party i.
SAMPLE OUTPUT (file cowpol.out):
3
2
*/
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::endl;
#include <list>
using std::list;
namespace sj
{
template<unsigned int size>
class UFSET
{
int p[size];
int rank[size];
public:
void MAKE_SET()
{
for (int i=0;i<size;rank[i++]=0) p[i]=i;
}
int FIND_SET(int x)
{
if (p[x]==x) return x;
else return p[x]=FIND_SET(p[x]);
}
void UNION(int x,int y)
{
x=FIND_SET(x);
y=FIND_SET(y);
if (x==y) return;
if (rank[x]<rank[y]) p[x]=y;
else
{
p[y]=x;
if (rank[x]==rank[y]) rank[x]++;
}
}
};
}
using namespace sj;
class Application
{
ifstream cin;
ofstream cout;
static const int MAXN=200000;
int N,K;
int A[MAXN+1],P[MAXN+1];
int size[MAXN+1];
int root;
list<int> child[MAXN+1];
int deep[MAXN+1];
int deepest[MAXN+1];
list<int> question[MAXN+1];
UFSET<MAXN+1> set;
bool visited[MAXN+1];
int ancestor[MAXN+1];
int dfs(int node,int depth=1,int father=0)
{
deep[node]=depth;
if (deep[deepest[A[node]]]<depth) deepest[A[node]]=node;
question[A[node]].push_back(node);
for (list<int>::iterator i=child[node].begin();
i!=child[node].end();i++)
if (*i!=father) dfs(*i,depth+1,node);
}
int LCA(int root)
{
static int depth;
static int _node[MAXN+1];
static int _father[MAXN+1];
static list<int>::iterator _i[MAXN+1];
_node[depth]=root;
_father[depth]=0;
_i[depth]=child[_node[depth]].begin();
ancestor[_node[depth]]=_node[depth];
for (;;)
{
int& node=_node[depth];
int& father=_father[depth];
list<int>::iterator& i=_i[depth];
if (*i==father) i++;
if (i!=child[node].end())
{
depth++;
_node[depth]=*i;
_father[depth]=node;
_i[depth]=child[_node[depth]].begin();
ancestor[_node[depth]]=_node[depth];
}
else
{
visited[node]=true;
if (node==deepest[A[node]])
{
for (list<int>::iterator i=question[A[node]].begin();
i!=question[A[node]].end();i++)
if (visited[*i])
{
int get=deep[node]+deep[*i]
-deep[ancestor[set.FIND_SET(*i)]]*2;
if (size[A[node]]<get) size[A[node]]=get;
}
}
else if (visited[deepest[A[node]]])
{
int get=deep[node]+deep[deepest[A[node]]]
-deep[ancestor[set.FIND_SET(deepest[A[node]])]]*2;
if (size[A[node]]<get) size[A[node]]=get;
}
depth–;
if (depth<0) break;
set.UNION(_node[depth],*_i[depth]);
ancestor[set.FIND_SET(*_i[depth])]=_node[depth];
_i[depth]++;
}
}
}
/*
int LCA(int node,int father=0)
{
ancestor[node]=node;
for (list<int>::iterator i=child[node].begin();
i!=child[node].end();i++)
if (*i!=father)
{
LCA(*i,node);
set.UNION(node,*i);
ancestor[set.FIND_SET(*i)]=node;
}
visited[node]=true;
if (node==deepest[A[node]])
{
for (list<int>::iterator i=question[A[node]].begin();
i!=question[A[node]].end();i++)
if (visited[*i])
{
int get=deep[node]+deep[*i]
-deep[ancestor[set.FIND_SET(*i)]]*2;
if (size[A[node]]<get) size[A[node]]=get;
//cout<<“LCA”<<node<<” “<<*i
// <<“=”<<ancestor[set.FIND_SET(*i)]<<endl;
}
}
else if (visited[deepest[A[node]]])
{
int get=deep[node]+deep[deepest[A[node]]]
-deep[ancestor[set.FIND_SET(deepest[A[node]])]]*2;
if (size[A[node]]<get) size[A[node]]=get;
//cout<<“LCA”<<node<<” “<<deepest[A[node]]
// <<“=”<<ancestor[set.FIND_SET(deepest[A[node]])]<<endl;
}
}
*/
public:
Application(const char* input,const char* output)
:cin(input),cout(output)
{
cin>>N>>K;
for (int i=1;i<=N;i++)
cin>>A[i]>>P[i];
}
~Application()
{
cin.close();
cout.close();
}
int run()
{
for (int i=1;i<=N;i++)
{
if (P[i]) child[P[i]].push_back(i);
else root=i;
child[i].push_back(P[i]);
}
dfs(root);
set.MAKE_SET();
LCA(root);
for (int i=1;i<=K;i++)
cout<<size[i]<<endl;
return 0;
}
};
int main()
{
static
Application app(“cowpol.in”,“cowpol.out”);
return app.run();
}