题意:
给一棵n个节点的树,最开始全部都是重点,现在有q个询问,每次给你一些轻点,并叫你输出整棵树的重点数量,
轻点可能会变为重点,如果这个轻点是两个重点的lca。
题解:
这里 我把有重点的子树叫重子树,一个重点都没有的子树叫轻子树。
一个轻点如果有两个重子树,那么这个轻点就会变为重点,可以画图试试。
然后我们就将轻点从树的最底层开始更新
x为这个点的子树个数,n为这个点的轻子树个数,
如果x-n=0,那么这个点的父亲节点的n就++
如果x-n<=1那么这个点就不能变会重点
最后统计一下轻点变回重点的个数
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std; const int N=1e5+;
int ic=,t,n,q;
int g[N],v[N*],nxt[N*],ed,dfs_idx,hsh[N]; struct node
{
int in,pre,n,x,col,idx;
bool operator < (const node &b)const{return in>b.in;}
}nd[N],tmp[N]; inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;} void init()
{
memset(g,,sizeof(g));
ed=,dfs_idx=;
} void dfs(int u=,int pre=)
{
nd[u].idx=u,nd[u].in=++dfs_idx,nd[u].pre=pre;
nd[u].col=,nd[u].n=,nd[u].x=;
for(int i=g[u];i;i=nxt[i])if(v[i]!=pre)nd[u].x++,dfs(v[i],u);
} int main(){
scanf("%d",&t);
while(t--)
{
printf("Case #%d:\n",ic++);
init();
scanf("%d%d",&n,&q);
F(i,,n-)
{
int x,y;
scanf("%d%d",&x,&y);
adg(x,y),adg(y,x);
}
dfs();
F(i,,q)
{
int nn,x;
int ans=;
scanf("%d",&nn);
F(j,,nn)scanf("%d",&x),tmp[j]=nd[x];
sort(tmp+,tmp++nn);
F(j,,nn)hsh[tmp[j].idx]=j;
F(j,,nn)
{
if(tmp[j].x-tmp[j].n<)tmp[j].col=;
if(tmp[j].x-tmp[j].n==)tmp[hsh[nd[tmp[j].idx].pre]].n++;
}
F(j,,nn)
{
if(tmp[j].col==)ans++;
hsh[tmp[j].idx]=;
}
printf("%d\n",ans+n-nn);
}
}
return ;
}