自动搬运

查看原文

来自洛谷，原作者为

	Perfound 死在了起跑线，死人一生平安

搬运于2025-08-24 22:50:10，当前版本为作者最后更新于2023-09-10 22:03:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里介绍一种不用考虑虚树根位置的方法。

首先求出所有节点子树内被选出的节点个数 $s_i$。

然后就可以发现虚树根位置就是 $s$ 最大的且深度最大的节点 $p$。

可以发现选出 $p$ 的儿子中 $s$ 最大的 $x$ 的子树内选出的节点不删，其他子树的删完是最优的方案。

然后就可以发现 $s_x$ 是严格第二大的，因为虚树根位置到根的 $s_i$ 肯定都相等且最大，而虚树根位置到根的节点肯定没有向外的子树中有被选的点。

于是直接线段树维护最大和严格第二大的值就好了。

#include<iostream>
#include<cstdio>
using namespace std;
#define N 1000010
#define l(p) p<<1
#define r(p) p<<1|1
struct edge{int next,to;}e[N];char s[10];bool usd[N];
int head[N],ip[N],st[N],ed[N],n,m,cnt,res;
int lt[N],pt[N],lz[N],id[N],idx,ipx;
struct sd{
	int a,b;
	void operator +=(const int &x){a+=x;if(~b)b+=x;}
	sd operator +(const sd &x){
		if(x.a>a)return (sd){x.a,max(x.b,a)};
		else if(x.a<a)return (sd){a,max(x.a,b)};
		else return (sd){x.a,max(x.b,b)};
	}
}mx[N];
void add(int a,int b){
	e[++cnt].to=b;
	e[cnt].next=head[a];
	head[a]=cnt;
}
void down(int p){
	mx[l(p)]+=lz[p],lz[l(p)]+=lz[p];
	mx[r(p)]+=lz[p],lz[r(p)]+=lz[p];
}
void app(int p,int l,int r,int i,int j,int k){
	if(i<=l&&r<=j){mx[p]+=k,lz[p]+=k;return;}
	if(lz[p])down(p),lz[p]=0;
	if(i<=((l+r)>>1))app(l(p),l,(l+r)>>1,i,j,k);
	if(j>((l+r)>>1))app(r(p),((l+r)>>1)+1,r,i,j,k);
	mx[p]=mx[l(p)]+mx[r(p)];
}
void dfs(int p,int f){
	ip[p]=1,pt[p]=f;
	for(int i=head[p];i;i=e[i].next){
		if(e[i].to==f)continue;
		dfs(e[i].to,p),ip[p]+=ip[e[i].to];
		if(ip[lt[p]]<ip[e[i].to])lt[p]=e[i].to;
	}
}
void cfs(int p,int f){
	if(lt[f]==p)ed[id[p]=id[f]]=p;
	else st[id[p]=++idx]=p;ip[p]=++ipx;
	if(lt[p])cfs(lt[p],p);
	for(int i=head[p];i;i=e[i].next)
		if(e[i].to!=f&&e[i].to!=lt[p])cfs(e[i].to,p);
}
void mak(int p,int k){
	for(;id[p]!=1;p=pt[st[id[p]]])
		app(1,1,n,ip[st[id[p]]],ip[p],k);
	app(1,1,n,1,ip[p],k),res+=k;
}
int main(){
	scanf("%d%d",&n,&m);for(int i=1;i<=n*4;i++)mx[i].b=-1;
	for(int i=1,a,b;i<n;i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
	dfs(1,0),cfs(1,0);
	for(int i=1,a;i<=m;i++){
		scanf("%s%d",s,&a);
		if(s[0]=='R'&&!usd[a])usd[a]=true,mak(a,1);
		else if(s[0]=='W'&&usd[a])usd[a]=false,mak(a,-1);
		printf("%d\n",res-mx[1].b);
	}
	return 0;
}