题解：P10238 [yLCPC2024] F. PANDORA PARADOXXX

· · 题解

删边不好做，所以正难则反，不断加边，然后考虑两个连通块的直径怎么合并，那合并之后的连通块的直径只可能是以下几种：

考虑直径怎么拼，新的直径的端点肯定是原来两个连通块的直径的端点中的两个。证明这个只需要证到任意点距离最远的点一定是直径的两个端点之一。

\text{proof.}

记 \text{d}(x,y) 表示点 x 和点 y 之间的距离，设直径的两个端点是 x,y，当前点是 u，不妨设 \text{d}(u,x)\leq \text{d}(u,y)。

运用反证法，若 \exists z\not =x,y，使 \text{d}(u,z)>\text{d}(u,y)，于是我们可以在直径中把 y 换成 z，于是 x 和 y 之间的路径不是直径，矛盾，所以 \text{d}(u,y) 一定大于所有 \text{d}(u,z)，\square。

运用树上差分和 \text{LCA} 求出两点间距离，然后就可以合并了。

代码不好写，所以上代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define int long long
using namespace std;
using ui = unsigned int;
using pii = pair<int, int>;
const int INF = 1e18;
const int N = 100005;
int n, q, fa[N], dep[N], siz[N], hson[N], top[N], dis[N], e[N], f[N], mx, ans[N];
vector<int> g[N], c[N];
vector<pii> edge;
pii dia[N];
bool vis[N];
void add(int u, int v, int w) { g[u].push_back(v), c[u].push_back(w); }
void dfs1(int u, int fath)
{
    fa[u] = fath, dep[u] = dep[fath] + 1, siz[u] = 1;
    for (ui i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i], w = c[u][i];
        if (v == fath) continue;
        dis[v] = dis[u] + w;
        dfs1(v, u), siz[u] += siz[v];
        if (!hson[u] || siz[v] > siz[hson[u]]) hson[u] = v;
    }
}
void dfs2(int u, int tp)
{
    top[u] = tp;
    if (hson[u]) dfs2(hson[u], tp);
    for (ui i = 0; i < g[u].size(); i++)
        if (g[u][i] != fa[u] && g[u][i] != hson[u]) dfs2(g[u][i], g[u][i]);
}
int LCA(int x, int y)
{
    while (top[x] != top[y]) dep[top[x]] < dep[top[y]] ? y = fa[top[y]] : x = fa[top[x]];
    return dep[x] < dep[y] ? x : y;
}
int d(int u, int v) { return dis[u] + dis[v] - 2 * dis[LCA(u, v)]; }
int getf(int x) { return f[x] == x ? x : f[x] = getf(f[x]); }
void merge(int x, int y)
{
    int fx = getf(x), fy = getf(y), tmp = 0;
    int tx[] = {dia[fx].first, dia[fx].second};
    int ty[] = {dia[fy].first, dia[fy].second};
    f[fy] = fx;
    int d1 = d(tx[0], tx[1]);
    int d2 = d(ty[0], ty[1]);
    if (d1 > tmp) tmp = d1, dia[fx] = {tx[0], tx[1]};
    if (d2 > tmp) tmp = d2, dia[fx] = {ty[0], ty[1]};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
        {
            int ds = d(tx[i], ty[j]);
            if (ds > tmp) tmp = ds, dia[fx] = {tx[i], ty[j]};
        }
    mx = max(mx, tmp);
}
signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
    {
        cin >> n >> q;
        mx = dis[1] = dep[0] = 0;
        edge.clear();
        edge.push_back({0, 0});
        for (int i = 1; i <= n; i++)
            g[i].clear(), c[i].clear(), f[i] = i, vis[i] = false, dia[i] = {i, i}, hson[i] = 0;
        for (int i = 1; i < n; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            edge.push_back({u, v});
            add(u, v, w), add(v, u, w);
        }
        dfs1(1, 0), dfs2(1, 1);
        for (int i = 1; i <= q; i++) cin >> e[i], vis[e[i]] = true;
        for (int i = 1; i < n; i++)
            if (!vis[i]) merge(edge[i].first, edge[i].second);
        for (int i = q; i >= 1; i--)
        {
            ans[i] = mx;
            merge(edge[e[i]].first, edge[e[i]].second);
        }
        for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    }
    return 0;
}