这场rank4，应该是暑假以来打的最好的一场了。。。
其它时候就没进过前10。。。
博弈 30pts
赛时 $ O(n^2) $ 暴力30pts；
对于暴力，我们能发现一个性质就是只要有一类边权出现了奇数次，那么先手必胜，所以我们枚举每一个点对，开个数组统计一下即可；
不要忘了离散化；
对于正解，用到了一个东西：$ xor-hashing $；
其实对于这种判断奇偶的问题，我们很容易想到 $ xor $，因为当有偶数个相同的数出现时， 他们 $ xor $ 起来的值是为 $ 0 $ 的，所以我们只需判断树上任意两点间的路径异或和是否为 $ 0 $ 即可；
那么我们做一下树上差分，记一下从根（指定一个）到每个点的异或和，然后找一下相同的减去其贡献即可（这是根据异或的性质：两个相同的数异或值为 $ 0 $， $ 0 \operatorname{xor} x = x $）；
但是我们发现这样并不能保证正确性，比如 $ 1 \operatorname{xor} 2 \operatorname{xor} 3 = 0 $，但这种情况是先手必胜，判断出来是后手必胜，出现了冲突；
发现这其实很像 $ hash $，所以我们可以给每类边权随一个在 $ unsigned \ long \ long $ 范围内的值，这样正确判断的概率就很大了；
随权值的操作可以用mt19937_64 来实现；
其实思路过程可能应该是点分治，不行再到树上差分，再到异或，再到 $ xor-hashing $（当然赛时可能到不了）；
这应该就是 $ xor-hashing $ 的基本应用了；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <ctime>
#include <cstdlib>
#include <random>
using namespace std;
int t;
int n;
int x[5000005], y[500005], w[500005], b[500005];
unsigned long long p[500005];
unsigned long long ha[500005];
map<unsigned long long, int> sum;
map<unsigned long long, bool> vis;
struct sss{
int t, ne;
unsigned long long w;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v, unsigned long long ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
e[cnt].w = ww;
}
void dfs(int x, int fa) {
sum[ha[x]]++;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa) continue;
ha[u] = ha[x] ^ e[i].w;
dfs(u, x);
}
}
long long ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937_64 ran(time(0));
cin >> t;
for (int i = 1; i <= 500000; i++) {
p[i] = ran();
}
while(t--) {
cin >> n;
cnt = 0;
ans = 0;
memset(h, 0, sizeof(h));
memset(ha, 0, sizeof(ha));
sum.clear();
vis.clear();
for (int i = 1; i <= n - 1; i++) {
cin >> x[i] >> y[i] >> w[i];
b[i] = w[i];
}
sort(b + 1, b + 1 + n - 1);
int len = unique(b + 1, b + 1 + n - 1) - b - 1;
for (int i = 1; i <= n - 1; i++) {
add(x[i], y[i], p[lower_bound(b + 1, b + 1 + len, w[i]) - b]);
add(y[i], x[i], p[lower_bound(b + 1, b + 1 + len, w[i]) - b]);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
if (sum[ha[i]] && !vis[ha[i]]) {
vis[ha[i]] = true;
ans += 1ll * (sum[ha[i]] * (sum[ha[i]] - 1) / 2);
}
}
cout << 1ll * n * (n - 1) / 2 - ans << '\n';
}
return 0;
}
大陆 100pts
赛时切了，还是首A。。。
其实这个题就是模拟一下即可；
考虑从下往上删子树，因为各个子树互不影响；
那么当我们回溯时，判断一下当前子树是否符合要求，若符合，则直接删掉；
这样我们会发现一个问题，就是可能会剩下一些点，这些点都和根组成一个连通块，且大小小于b；
那么我们想要把它们并入一个其它的，已划分出的连通块去，那么这个连通块的大小要小于等于2倍的b；
所以我们把划分条件改一下，当一棵子树的大小大于等于b且小于等于2倍的b时，就把它划出去；
那这样我们还会出现另一个问题，就是当一棵子树的子树很多时，可能出现这棵子树的大小大于2倍的b，但它的任意一棵子树的大小都小于b的情况，对于这种情况，我们直接单独考虑，每b个划分一次，不足b个的并入先前的连通块中，这样就满足要求了；
这样的话，我们划分出的最后一个连通块可能会大于2倍的b，小于3倍的b，这样就不能使根节点连的块并入此块，所以我们将这颗子树的根并入第一个连通块，因为第一个连通块大小是小于等于2倍的b的，这样就可以使根节点连的块并入第一个块了；
这题还是可以练练搜索能力的；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, b;
struct sss{
int t, ne;
}e[50005];
int h[50005], cnt;
void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
int siz[50005];
int c[50005], tot, cap[50005], sum[50005], fa[50005];
int aa;
void dfs(int x, int f) {
siz[x] = 1;
fa[x] = f;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == f) continue;
dfs(u, x);
siz[x] += siz[u];
}
}
void cfs(int x) {
c[x] = tot;
sum[tot]++;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa[x] || c[u]) continue;
cfs(u);
}
}
void efs(int x) {
int su = 0;
int ssu = 0;
tot++;
cap[tot] = x;
sum[tot]++;
c[x] = tot; //并入第一个块；
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa[x]) continue;
if (c[u]) continue;
su += siz[u];
ssu += siz[u];
cfs(u);
if (su >= b) {
tot++;
if (siz[x] - ssu - 1 < b) {
tot--;
}
cap[tot] = x;
su = 0;
}
}
}
void afs(int x) {
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa[x]) continue;
afs(u);
}
if (siz[x] >= b && siz[x] <= 2 * b) {
tot++;
cap[tot] = x;
cfs(x);
for (int i = fa[x]; i; i = fa[i]) {
siz[i] -= siz[x];
}
} else if (siz[x] > 2 * b) {
efs(x);
for (int i = fa[x]; i; i = fa[i]) {
siz[i] -= siz[x];
}
}
}
void ddfs(int x, int fa) {
if (c[x]) {
aa = c[x];
return;
}
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa) continue;
ddfs(u, x);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> b;
int x, y;
for (int i = 1; i <= n - 1; i++) {
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(1, 0);
if (siz[1] >= b && siz[1] <= 3 * b) {
cout << 1 << '\n';
for (int i = 1; i <= n; i++) {
cout << 1 << ' ';
}
cout << '\n';
cout << 1;
return 0;
}
afs(1);
if (!c[1]) {
aa = 0;
ddfs(1, 0);
for (int i = 1; i <= n; i++) {
if (!c[i]) c[i] = aa;
}
}
cout << tot << '\n';
for (int i = 1; i <= n; i++) {
cout << c[i] << ' ';
}
cout << '\n';
for (int i = 1; i <= tot; i++) {
cout << cap[i] << ' ';
}
return 0;
}