题目
给定一棵有根树，树上的每个节点是黑色或白色的。1 号点是根。
请对于每个白色的点，在子树中找一个黑色的点与其匹配，其中每个黑点只能和一个白点匹配。你需要求出所有白点与其配对的黑点的距离之和最小是多少。
树上两点的距离定义为他们之间简单路径上的边数。
数据保证有解。
1<n<106
题解
首先可以考虑到贪心
如果以白点为主体，可以从深到浅枚举白点（因为深处的白点可选的黑点更少），然后对于每个白点维护子树里面里它最近的黑点，配对即可。
不过这么做似乎要可并堆我不会，todo
所以考虑以黑点为主体，可以从浅到深枚举黑点（因为浅处的黑点选择更少），对于每个黑点找到它到根节点路径上的最深的，且未被配对的白点，具体可以用并查集维护，看代码
代码
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
bool color[N];
int fa[N], depth[N];
int head[N], nxt[N << 1], to[N << 1], cnt;
int vis[N];
long long white_dis_sum;
int vis_of_p[N];
void add(int x, int y)
{
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs(int u, int anc, int first_white)
{
depth[u] = depth[anc] + 1;
fa[u] = first_white;
if(color[u] == 0) white_dis_sum += depth[u];
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(v == anc) continue;
if(color[u])
{
dfs(v, u, first_white);
}
else
{
dfs(v, u, u);
}
}
}
int findfa_with_vis_equals_to_0(int u)
{
if(u == -1 || u == 0x3f3f3f3f) return 0x3f3f3f3f;
if(vis[u] == 0) return u;
return fa[u] = findfa_with_vis_equals_to_0(fa[u]);
}
int main()
{
freopen("wbtree.in", "r", stdin);
freopen("wbtree.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
cin >> color[i];
int u, v;
for(int i = 1;i <= n - 1;i++)
{
cin >> u >> v;
add(u, v), add(v, u);
}
dfs(1, 0, -1);
queue <int> qwq;
qwq.push(1);
long long ans = 0;
while(qwq.size())
{
int t = qwq.front();
vis_of_p[t] = 1;
for(int i = head[t]; i; i = nxt[i])
{
int v = to[i];
if(vis_of_p[v]) continue;
qwq.push(v);
}
qwq.pop();
if(color[t] == 0) continue;
int deepest_white = findfa_with_vis_equals_to_0(fa[t]);
if(deepest_white == 0x3f3f3f3f) continue;
vis[deepest_white] = 1;
ans += depth[t];
}
cout << ans - white_dis_sum;
return 0;
}
|