树（tree）
时间限制：C/C++ 2000MS，其他语言 4000MS
内存限制：C/C++ 256MB，其他语言 512MB描述
给定一个 \(n\) 个结点，\(n−1\) 条边的有根树。
第 \(i\) 条边可以用 (\(a_i,b_i\)) 来描述，它表示连接结点 \(a_i\) 和结点 \(b_i\) 的一条边，其中结点 \(a_i\) 是结点 \(b_i\) 的父节点。
一共有 \(n−1\) 次查询：第 \(i\) 次查询包含一个整数 \(c_i\)，询问由前 \(i\) 条边构成的图（森林）中从结点 \(c_i\) 开始的最长简单路径的长度。
数据保证不存在 \(j\) 使得 \(1≤j≤i\) 且 \(b_j=c_i\)，即 \(c_i\) 是前 \(i\) 条边构成的森林中一棵树的根。输入描述
输入有多组测试用例，第一行包含一个整数 \(t(1≤t≤10^5)\) ，表示接下来有 \(t\) 组测试用例。
每组测试用例第一行包含一个整数 \(n(2≤n≤10^6)\)，表示树的结点数。
接下来 \(n−1\) 行每行包含三个整数 \(a_i,b_i,c_i\) \((1≤a_i,b_i,c_i≤n,a_i≠b_i)\)，表示结点 \(b_i\) 的父结点是结点 \(a_i\) ，第 \(i\) 次询问是 \(c_i\)。
数据保证：
对每一个测试用例，\(n−1\) 条边形成一个有根树。
对每一个测试用例，对任意 \(1≤i≤n−1\)，保证不存在 \(j\) 使得 \(1≤j≤i\) 且 \(b_j=c_i\)。
所有测试用例中，\(n\) 的总和不超过 \(10^6\)输出描述
对每一个测试用例，一行输出 \(n−1\) 个整数，第 \(i\) 个整数表示第 \(i\) 次询问的答案。
用例输入 1
6 4 3 4 1 2 3 1 1 2 1 4 3 4 3 2 1 2 3 2 3 4 1 2 1 3 4 3 2 3 1 4 2 3 1 2 4 2 1 2 1 2 1 2 1 2 2 1 2用例输出 1
0 0 3 1 1 2 1 1 3 0 1 2 1 1用例输入 2
2 5 1 2 3 1 3 4 3 4 1 1 5 1 15 10 14 10 5 8 5 1 3 1 4 7 10 2 5 2 1 2 1 3 4 1 9 10 9 11 13 11 5 6 1 10 12 9 8 9 1 11 15 11 7 11 1用例输出 2
0 0 2 2 1 1 1 1 2 3 3 2 1 3 2 6 1 6提示
\(1≤t≤10^5\)
\(2≤n≤10^6\)
解析
由题意得 \(c_i\) 为某树的根；
由于不可能将两个非根结点连接在一起，所以 \(b_i\) 一定是树根。
用带权并查集处理深度和子树的最大深度即可。
代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
return x*w;
}
const int N=2e6+5,M=5e6+5;
int T,n;
int fa[N],dist[N],maxdep[N];
inline void uInit()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
maxdep[i]=dist[i]=0;
}
return;
}
int uask(const int x)
{
if(fa[x]==x) return x;
else
{
const int oldfa=fa[x];
fa[x]=uask(fa[x]);
dist[x]=dist[x]+dist[oldfa];
maxdep[fa[x]]=max(maxdep[fa[x]],dist[x]); //ÕâÒ»ÐпÉÒÔÊ¡ÂÔ
return fa[x];
}
}
inline void umerge(const int x,const int y)
{
const int rtx=uask(x),rty=uask(y);
if(rtx==rty) return;
fa[rty]=rtx;
dist[rty]=dist[x]+1-dist[y]; //dist[y]+dist[rty]=dist[x]+dis(x,y)
maxdep[rtx]=max(maxdep[rtx],maxdep[rty]+dist[rty]);
return;
}
int main()
{
T=read();
while(T--)
{
n=read();
uInit();
for(int i=1;i<n;i++)
{
int a=read(),b=read(),q=read();
umerge(a,b);
printf("%d ",maxdep[q]);
}
putchar('\n');
}
return 0;
}