首页 > 代码库 > hdu_5927_Auxiliary Set(xjb搞)

hdu_5927_Auxiliary Set(xjb搞)

2024-08-15 20:21:57   217人阅读

题目链接：hdu_5927_Auxiliary Set

题意：

给一棵n个节点的树，最开始全部都是重点，现在有q个询问，每次给你一些轻点，并叫你输出整棵树的重点数量，

轻点可能会变为重点，如果这个轻点是两个重点的lca。

题解：

这里 我把有重点的子树叫重子树，一个重点都没有的子树叫轻子树。

一个轻点如果有两个重子树，那么这个轻点就会变为重点，可以画图试试。

然后我们就将轻点从树的最底层开始更新

x为这个点的子树个数，n为这个点的轻子树个数，

如果x-n=0，那么这个点的父亲节点的n就++

如果x-n<=1那么这个点就不能变会重点

最后统计一下轻点变回重点的个数

 

技术分享
 1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4  5 const int N=1e5+7; 6 int ic=1,t,n,q; 7 int g[N],v[N*2],nxt[N*2],ed,dfs_idx,hsh[N]; 8  9 struct node10 {11     int in,pre,n,x,col,idx;12     bool operator < (const node &b)const{return in>b.in;}13 }nd[N],tmp[N];14 15 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}16 17 void init()18 {19     memset(g,0,sizeof(g));20     ed=0,dfs_idx=0;21 }22 23 void dfs(int u=1,int pre=0)24 {25     nd[u].idx=u,nd[u].in=++dfs_idx,nd[u].pre=pre;26     nd[u].col=1,nd[u].n=0,nd[u].x=0;27     for(int i=g[u];i;i=nxt[i])if(v[i]!=pre)nd[u].x++,dfs(v[i],u);28 }29 30 int main(){31     scanf("%d",&t);32     while(t--)33     {34         printf("Case #%d:\n",ic++);35         init();36         scanf("%d%d",&n,&q);37         F(i,1,n-1)38         {39             int x,y;40             scanf("%d%d",&x,&y);41             adg(x,y),adg(y,x);42         }43         dfs();44         F(i,1,q)45         {46             int nn,x;47             int ans=0;48             scanf("%d",&nn);49             F(j,1,nn)scanf("%d",&x),tmp[j]=nd[x];50             sort(tmp+1,tmp+1+nn);51             F(j,1,nn)hsh[tmp[j].idx]=j;52             F(j,1,nn)53             {54                 if(tmp[j].x-tmp[j].n<2)tmp[j].col=0;55                 if(tmp[j].x-tmp[j].n==0)tmp[hsh[nd[tmp[j].idx].pre]].n++;56             }57             F(j,1,nn)58             {59                 if(tmp[j].col==1)ans++;60                 hsh[tmp[j].idx]=0;61             }62             printf("%d\n",ans+n-nn);63         }64     }65     return 0;66 }
View Code

 

hdu_5927_Auxiliary Set(xjb搞)


联系
我们