自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 21:48:06，当前版本为作者最后更新于2023-05-28 16:09:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

套路题。

容易想到时光倒流，将删边转化为加边，每次操作即为合并两个连通块。

不妨以 $1$ 为根，设 $\operatorname{val}(u)$ 表示 $u$ 到根路径权值异或和，那么同一连通块内的两个点 $u,v$ 之间路径权值异或和为 $0$，当且仅当 $\operatorname{val}(u)=\operatorname{val}(v)$。

如果我们对每个连通块维护一个桶，那么合并的时候只需要枚举一个桶中的元素，在另一个桶中统计答案，并把两个桶合并即可。枚举哪个桶都行，我们枚举更小的桶，更新完答案再暴力插入更大的桶即可。换句话说就是每个连通块维护 map，并进行启发式合并。

时间复杂度 $\mathcal O(n\log^2n)$。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprllf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randll(ll L, ll R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 1e5+5;

ll n, U[N], V[N], W[N], p[N], val[N], dsu[N], ans[N];
vector<tuple<ll, ll>> e[N];
map<ll, ll> mp[N];

ll find(ll x) {return x == dsu[x] ? x : dsu[x] = find(dsu[x]);}

void dfs(ll u, ll f) {
    for(auto&& [v, w] : e[u]) {
        if(v != f) {
            val[v] = val[u] ^ w;
            dfs(v, u);
        }
    }
}

int main() {
    scanf("%lld", &n);
    rep(i, 1, n-1) {
        scanf("%lld%lld%lld", &U[i], &V[i], &W[i]);
        e[U[i]].emplace_back(V[i], W[i]);
        e[V[i]].emplace_back(U[i], W[i]);
    }
    rep(i, 1, n-1) scanf("%lld", &p[i]);
    dfs(1, 0);
    rep(i, 1, n) dsu[i] = i;
    rep(i, 1, n) mp[i][val[i]] = 1;
    ll now = 0;
    per(i, n-1, 1) {
        ll u = find(U[p[i]]), v = find(V[p[i]]);
        if((ll)mp[u].size() < (ll)mp[v].size()) swap(u, v);
        for(auto&& [key, cnt] : mp[v]) {
            now += cnt * mp[u][key];
            mp[u][key] += cnt;
        }
        map<ll, ll>().swap(mp[v]);
        dsu[v] = u;
        ans[i] = now;
    }
    rep(i, 1, n) printf("%lld\n", ans[i]);
    return 0;
}