题面
原题链接
大秦 为你打开 题目传送门
题目翻译
你有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一条路径 $P(u,v)$ 的权值为经过的所有点的点权的异或和。定义一棵树是合法的，当且仅当树上所有简单路径（只经过每个点一次的路径）的的权值都不为 $0$。
你可以对权值进行修改，可以改成任意正整数，问最少修改多少次才能让这棵树合法。
输出最小修改次数。
$n\leq 2\times 10^5,a_i\leq 2^{30}$
思路
我们不难发现，如果一条路径上的元素异或值为 0 我们设 $dep_i$ 表示 $i$ 号点到根所有路径的值。 那么这个路径一定满足条件 $dep_u\ \oplus\ dep_v\ \oplus\ dep_{lca(u,v)} = 0$ 。那么我们就不难想到，处理出这个节点所有儿子的左右子树里的 dep 值。如果 $v$ 的子树之中存在一个值等于 $u$ 的子树中的一个节点的值异或当前这个节点的值，那么一定存在一条路径在这两个子树之中。那么一劳永逸的方式就是把当前这个作为 lca 的节点替换了，统计答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 2e5 + 10;
template<int N, int M>
class Graph {
private :
struct Edge {
int to, nt, wt;
Edge() {}
Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
}e[M];
int hd[N], cnte;
public :
inline void AddEdge(int u, int v, int w = 0) {
e[++cnte] = Edge(v, hd[u], w);
hd[u] = cnte;
}
inline int head(int u) { return hd[u]; }
inline int nt(int u) { return e[u].nt; }
inline int to(int u) { return e[u].to; }
inline int wt(int u) { return e[u].wt; }
};
int n;
int a[N];
Graph< N , N << 1 >G;
inline void Input() {
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
int u, v;
for(int i = 1; i < n; i++) {
read(u, v);
G.AddEdge(u, v);
G.AddEdge(v, u);
}
}
int ans;
set<int >st[N];
int dep[N];
inline void Dfs(int u, int fa) {
dep[u] = dep[fa] ^ a[u];
st[u].insert(dep[u]);
int flag = 0;
for(int i = G.head(u); i; i = G.nt(i)) {
int v = G.to(i);
if(v == fa) continue;
Dfs(v, u);
if(st[u].size() < st[v].size()) st[u].swap(st[v]);
for(auto &p : st[v]) if(st[u].count(p ^ a[u])) flag = 1;
for(auto &p : st[v]) st[u].insert(p);
}
if(flag) ans++, st[u].clear();
}
inline void Work() {
Dfs(1, 0);
printf("%d\n", ans);
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
