比赛 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;

}