题目链接 Problems
Problem A
Problem B
bitset……
Problem C
Problem D
Problem E
Problem F
Problem G
考虑最小生成树的时候，
合并两个点的时候就新建一个点，把这两个点都指向新的那个点。
然后给这两个点都打上delta标记。
最后dfs这棵新的树就好了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define fi first #define se second typedef unsigned long long LL; const int N = 4e5 + 10; const int M = 3e5 + 10; struct node{ int x, y; LL z; friend bool operator < (const node &a, const node &b){ return a.z < b.z; } } e[M]; int T; int n, m; int father[N]; int id; int ca = 0; LL sz[N]; LL delta[N]; LL ans[N]; vector <int> v[N]; int getfather(int x){ return father[x] == x ? x : father[x] = getfather(father[x]); } void dfs(int x, LL ss){ if (x <= n) ans[x] = ss; for (auto u : v[x]){ dfs(u, ss + delta[u]); } } int main(){ scanf("%d", &T); while (T--){ scanf("%d%d", &n, &m); rep(i, 1, n) father[i] = i; rep(i, 0, n * 3) sz[i] = 0, delta[i] = 0; rep(i, 1, n) sz[i] = 1; rep(i, 0, n * 3) v[i].clear(); rep(i, 1, m){ scanf("%d%d%llu", &e[i].x, &e[i].y, &e[i].z); } id = n; sort(e + 1, e + m + 1); rep(i, 0, n * 2) ans[i] = 0; rep(i, 1, m){ int x = e[i].x, y = e[i].y; LL z = e[i].z; int fx = getfather(x), fy = getfather(y); if (fx == fy) continue; ++id; v[id].push_back(fx); v[id].push_back(fy); sz[id] = sz[fx] + sz[fy]; father[fx] = id; father[fy] = id; father[id] = id; delta[fx] = z * sz[fy]; delta[fy] = z * sz[fx]; } dfs(id, 0); LL ret = 0; rep(i, 1, n) ret ^= ((LL)i * ans[i]); printf("Case #%d: %llu\n", ++ca, ret); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/8846711.html
