题解：2024牛客暑期多校第4场——A [LCT]

英文题干

Note the unusual memory limit for this problem.

Given a rooted tree with n nodes and n-1 edges. The i-th edge can be described by $(a_i, b_i)$ , which represents an edge connecting node $a_i$ and node $b_i$ , where node $a_i$ is the parent of node $b_i$ .

There are n-1 queries. The i-th query contains an integer $c_i$ , asking for the length of the longest simple path starting from node $c_i$ in the graph (forest) formed by the first i edges. It is guaranteed that there does not exist j such that $1 ≤ j ≤ i$ and $b_j$ = $c_i$ , i.e., $c_i$ is the root of a tree in the forest.

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t(1\leq t\leq 10^5)$ . The description of the test cases follows.

The first line of each test case contains an integer $n(2\leq n\leq 10^6)$ , representing the number of nodes in the tree.

The next n−1 lines each contain three integers $a_i,b_i,c_i$ ， $(1\leq a_i,b_i,c_i\leq n, a_i\neq b_i)$ , representing that the parent of node $b_i$ is $a_i$ , and the i-th query is $c_i$ .

It is guaranteed that: For each test case, the n−1 edges form a rooted tree.

For each test case, for any $1\leq i\leq n-1$ , there does not exist j such that $1\leq j\leq i$ and $b_j$ = $c_i$ .

The sum of n over all test cases does not exceed $10^6$ .

Output:

For each test case, output n−1 integers in one line. The i-th integer represents your answer to the i-th query.

中文题干

注意这个问题的特殊的内存限制。(131072K，比正常的262144K少一半)

给定一个有 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$ 是森林中一棵树的根。

思路

一道维护附加信息的并查集，最开始题目理解错了导致浪费了好多时间qaq （题目输入保证是森林的，说明 $b_i$ 一定是某颗树的根，否则 $b_i$ 有两个父节点）

除了基本并查集自带的所属组（group）之外，我们额外维护最长路径和深度两个数组。深度在每次寻根的时候进行累计，节点越往下深度越大。
由于查询的点只限树根，因此在每次合并的时候要更新树根（a的根节点）的最长路径数组。

AC代码

时间复杂度：O( $Tn$ )

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1e6 + 10;

ll ans[maxn];  // 节点 i 的最长路径
ll depth[maxn];  // 节点 i 的深度

// 并查集
int group[maxn];
inline int findroot(int x)
{
    if (x != group[x]) {
        int tmp = group[x];
        group[x] = findroot(group[x]);
        depth[x] += depth[tmp];  // 深度累计（越往下值越大）
    }
    return group[x];
}
inline void unite(int x, int y)
{
    int fx = findroot(x);
    int fy = findroot(y);
    if (fx != fy)
    {
        group[fy] = fx;
        depth[y] = depth[x] + 1;
        ans[fx] = max(ans[fx], ans[y] + depth[y]);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        for (int i = 1; i <= n; i++) {
            group[i] = i;
            depth[i] = 0;
            ans[i] = 0;
        }

        for (int i = 1; i <= n - 1; i++) {
            int u, v, req;
            cin >> u >> v >> req;

            unite(u, v);
            cout << ans[req] << " ";
        }
        cout << "\n";
    }

    return 0;
}