題目#
給定一棵有根樹，樹上的每個節點是黑色或白色的。$1$ 號點是根。
請對於每個白色的點，在子樹中找一個黑色的點與其匹配，其中每個黑點只能和一個白點匹配。你需要求出所有白點與其配對的黑點的距離之和最小是多少。
樹上兩點的距離定義為他們之間簡單路徑上的邊數。
數據保證有解。
$1 < n < 10^6$
題解#
首先可以考慮到貪心
如果以白點為主體，可以從深到淺枚舉白點（因為深處的白點可選的黑點更少），然後對於每個白點維護子樹裡面裡它最近的黑點，配對即可。
不過這麼做似乎要可並堆我不會，todo
所以考慮以黑點為主體，可以從淺到深枚舉黑點（因為淺處的黑點選擇更少），對於每個黑點找到它到根節點路徑上的最深的，且未被配對的白點，具體可以用並查集維護，看代碼
代碼#
#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]/*black*/)
{
dfs(v, u, first_white);
}
else/*white*/
{
dfs(v, u, u);
}
}
}
int findfa_with_vis_equals_to_0(int u)
{
// cout << "qaq" << u << endl;
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()
{
// for(int i = 1;i <= n;i++)
// {
// fa[i] = i;
// }
// clock_t c1 = clock();
// #ifdef LOCAL
freopen("wbtree.in", "r", stdin);
freopen("wbtree.out", "w", stdout);
// #endif
//----------------------------------------
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);
}
//找不到就是-1
dfs(1, 0, -1);
queue <int> qwq;
qwq.push(1);
long long ans = 0;
// for(int i = 1;i <= n;i++)
// {
// cout << i << ": " << fa[i] << endl;
// }
while(qwq.size())
{
int t = qwq.front();
// cout << "qwq"<<t << endl;
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]);
// cout << t << "的deepest_white: " << deepest_white << endl;
if(deepest_white == 0x3f3f3f3f) continue;
vis[deepest_white] = 1;
ans += depth[t];
}
cout << ans - white_dis_sum;
//----------------------------------------
//end:
// cerr << "Time Used:" << clock() - c1 << "ms" << endl;
return 0;
}
/*
* ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐
* └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤
* │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│ Space │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/