SenseTime Ace Coder Challenge 暨 商汤在线编程挑战赛*

题目链接   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;

}

SenseTime Ace Coder Challenge 暨 商汤在线编程挑战赛*的相关教程结束。