比赛 |
20241129 |
评测结果 |
AAAAAAAAAA |
题目名称 |
路径覆盖 |
最终得分 |
100 |
用户昵称 |
darkMoon |
运行时间 |
0.438 s |
代码语言 |
C++ |
内存使用 |
9.36 MiB |
提交时间 |
2024-11-29 11:59:34 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
auto IN = freopen("lucover.in", "r", stdin);
auto OUT = freopen("lucover.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 1e5 + 5;
int n = mread(), q = mread(), f[N][2][2], ans[N], fa[N], g[N][3];
// f_{x, 0/1, 0/1} 表示 x 点,偶/奇度数,上一个从第一个/第二个方程转移过来
vector<int> v[N];
// f[x][0] = min(f[x][0] + f[y][2], f[x][1] + min(f[y][0], f[y][1]));
// f[x][1] = min(f[x][1] + f[y][2], tmp + min(f[y][0], f[y][1]) + 1);
void dfs1(int x, int fa){
g[x][2] = 1;
f[x][1][0] = f[x][1][1] = g[x][1] = 0;
f[x][0][0] = f[x][0][1] = g[x][0] = 0x3f3f3f3f;
::fa[x] = fa;
for(int y : v[x]){
if(y == fa){
continue;
}
dfs1(y, x);
f[x][0][0] = g[x][0] + g[y][2];
f[x][0][1] = g[x][1] + min(g[y][0], g[y][1]);
f[x][1][0] = g[x][1] + g[y][2];
f[x][1][1] = g[x][0] + min(g[y][0], g[y][1]) + 1;
g[x][2] += min(g[y][0] + 1, g[y][1]);
g[x][0] = min(f[x][0][0], f[x][0][1]);
g[x][1] = min(f[x][1][0], f[x][1][1]);
}
return;
}
void dfs2(int x, int fa){
if(x != 1){
int t[3] = {0};
// t 是 fa 的 g
t[0] = max(g[fa][0] - g[x][2], g[fa][1] - min(g[x][0], g[x][1]) - 1);
t[1] = max(g[fa][1] - g[x][2], g[fa][0] - min(g[x][0], g[x][1]));
t[2] = g[fa][2] - min(g[x][0] + 1, g[x][1]);
// printf("*** %lld %lld %lld %lld %lld %lld %lld\n", x, fa, t[0], t[1], t[2]
// , f[fa][0][0] - g[x][2], f[fa][1][1] - min(g[x][0], g[x][1]) - 1);
f[x][0][0] = g[x][0] + t[2];
f[x][0][1] = g[x][1] + min(t[0], t[1]);
f[x][1][0] = g[x][1] + t[2];
f[x][1][1] = g[x][0] + min(t[0], t[1]) + 1;
g[x][2] += min(t[0] + 1, t[1]);
g[x][0] = min(f[x][0][0], f[x][0][1]);
g[x][1] = min(f[x][1][0], f[x][1][1]);
}
// printf("*** %lld %lld %lld %lld\n", x, g[x][0], g[x][1], g[x][2]);
for(int y : v[x]){
if(y == fa){
continue;
}
dfs2(y, x);
}
return;
}
signed main(){
for(int i = 1, x, y; i < n; i ++){
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 0);
while(q --){
int x = mread();
// dfs1(x, 0);
printf("%lld\n", g[x][2]);
}
return 0;
}