A. LCT

题意概括

有一棵n个点的树， n - 2条边，每次给出 , , 保证前者为后者的父亲， 再给出一个询问, 保证是根不是儿子，问从开始的最长简单路径的长度。

思路

1. 最长简单路径的长度， 实际上就是以为根的树的高度
2. 我们就可以去维护每颗树的高度， 那应该怎么去维护呢？尤其是合并的时候
   看这个
3. 所以还要维护树的深度
4. 那就要用到带权并查集了

代码

#include <bits/stdc++.h>
int fa[1000010] = {0};
int dis[1000010] = {0}; // dis[i] i点的深度， 就是i距离fa[i]的距离
int ans[1000010] = {0};
int find(int x)
{
    if (x == fa[x]) return x;
    int t = fa[x];
    fa[x] = find(fa[x]);
    dis[x] += dis[t];
    return fa[x];
}

void Merge(int x, int y)
{
    int xx = find(x), yy = find(y);
    fa[yy] = xx;
    dis[y] = dis[x] + 1;
    ans[xx] = std::max(ans[xx], dis[x] + ans[yy] + 1);
}

void solve()
{
    int n = 0, u = 0, v = 0, c= 0;
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        dis[i] = 0;
        ans[i] = 0;
    }
    for (int i = 1; i <= n - 1; i++)
    {
        std::cin >> u >> v >> c; // u是父亲， v是儿子
        Merge(u, v);
        std::cout << ans[c] << " ";
    }
    std::cout << std::endl;
}


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 0;
    std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}