P9620 歌姬 题解

· · 题解

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

首先求出所有节点子树内被选出的节点个数 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;
}