比赛 |
20241129 |
评测结果 |
AAAAAAAAAA |
题目名称 |
路径覆盖 |
最终得分 |
100 |
用户昵称 |
┭┮﹏┭┮ |
运行时间 |
0.316 s |
代码语言 |
C++ |
内存使用 |
14.87 MiB |
提交时间 |
2024-11-29 10:17:47 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 2e5+10;
ll read(){
ll x = 0,f = 1;char c = getchar();
for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
return x * f;
}
int n,q;
vector<int>e[N];
int f[N][2],g[N],son[N];
vector<int>s[N];
// f[x][1] 已连接 x -> fa,g[x] 表示 x 的固定二操作
void dfs1(int x,int fa){
f[x][1] = g[x] = 1;
for(int y : e[x]){
if(y == fa)continue;
dfs1(y,x),son[x]++;
int w = f[y][0];
g[x] += w;
if(g[y] < f[y][1])f[x][0] += g[y],son[x]--;
else f[x][0] += f[y][1];
// sum += w;
}
f[x][1] = f[x][0] -= son[x] / 2;
if(son[x] % 2 == 0)f[x][1]++;
}
void dfs2(int x,int fa){
for(int y : e[x]){
if(y == fa)continue;
int s1 = 1,s2 = 1;
if(g[y] < f[y][1])s1--;
int tmp0 = f[x][0] - (son[x] - s1) / 2 + son[x] / 2,tmp1 = f[x][1] - (son[x] - s1) / 2 + son[x] / 2,tmp2 = g[x];
if(son[x] % 2 == 0)tmp1--;
if((son[x] - s1) % 2 == 0)tmp1++;
if(g[y] < f[y][1])tmp0 -= g[y],tmp1 -= g[y];
else tmp0 -= f[y][1],tmp1 -= f[y][1];
tmp2 -= min(f[y][0],f[y][1]);
g[y] += tmp0;
if(tmp2 < tmp1)f[y][0] += tmp2,s2--;
else f[y][0] += tmp1;
f[y][1] = f[y][0] = f[y][0] - (son[y] + s2) / 2 + son[y] / 2;
son[y] += s2;
if(son[y] % 2 == 0)f[y][1]++;
dfs2(y,x);
}
}
int main(){
freopen("lucover.in","r",stdin);
freopen("lucover.out","w",stdout);
n = read(),q = read();
for(int i = 1;i < n;i++){
int x = read(),y = read();
e[x].pb(y),e[y].pb(x);
}
dfs1(1,0);
dfs2(1,0);
for(int i = 1;i <= q;i++){
int x = read();
// memset(f,0,sizeof f);
// memset(son,0,sizeof son);
// memset(g,0,sizeof g);
// dfs1(x,0);
printf("%d\n",g[x]);
}
return 0;
}