codeforces 1044F DFS dfs序+线段树

曾经终败给现在 2022-01-22 22:25 236阅读 0赞

## 题意：给一颗初始树，然后有q次操作，每次操作一对点，如果这对点有边，就删除边（保证不删除初始的树边），否则，就加一条边，接下来你可以从某个点dfs搜索，如果搜索出来的边和初始树的边一样，那这个点就是好的点，求每次操作后有多少个好的点。 ##

## 思路：首先对初始的树走一遍dfs序，l\[u\]表示u这个节点的dfs序号，r\[u\]表示以u为根的子树的序号最大的那个点序号，接下来看图分析。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Njc3VfY2F0_size_16_color_FFFFFF_t_70][]

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Njc3VfY2F0_size_16_color_FFFFFF_t_70 1][] ##

## 假设加入x y这条边，我们发现，只要在x y围成的环内的点或者是直接连接到环内点的点，都不是“好的”点，因此线段树更新环内以及环内连接的所有点即可，每次用n-不合格的点就是答案。 ##

## 参考博客：[https://blog.csdn.net/ccsu\_cat/article/details/83892646][https_blog.csdn.net_ccsu_cat_article_details_83892646] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=2e5+10;
    vector<int>G[maxn];
    map<int,int>mp[maxn];
    int sum[maxn*4],Set[maxn*4],dep[maxn];
    int l[maxn],r[maxn],f[maxn][20],cnt=0;
    ///dfs序
    void dfs(int u,int fa,int deep){
    	f[u][0]=fa;
    	dep[u]=deep;
    	l[u]=++cnt;
    	for(int i=0;i<G[u].size();i++)
    	if(G[u][i]!=fa)
            dfs(G[u][i],u,deep+1);
    	r[u]=cnt;
    }
    ///Set标记去重
    void pushup(int o,int ls,int rs,int l,int r){
    	if(Set[o])sum[o]=r-l+1;
    	else if(l==r)sum[o]=0;
    	else sum[o]=sum[ls]+sum[rs];
    }
    ///线段树区间更新
    void up(int o,int l,int r,int ql,int qr,int v){
    	if(l>r)return;
    	int m=(l+r)/2,ls=o*2,rs=o*2+1;
    	if(l>=ql&&r<=qr){
    		Set[o]+=v;
    		pushup(o,ls,rs,l,r);
    		return;
    	}
    	if(ql<=m)up(ls,l,m,ql,qr,v);
    	if(qr>m)up(rs,m+1,r,ql,qr,v);
    	pushup(o,ls,rs,l,r);
    }
    int main(){
    	int n,q,x,y,u,v;
    	scanf("%d%d",&n,&q);
    	for(int i=1;i<n;i++){
    		scanf("%d%d",&u,&v);
    		G[u].push_back(v);
    		G[v].push_back(u);
    	}
    	dfs(1,0,1);
    	///预处理st表
    	for(int j=1;j<20;j++)
            for(int i=1;i<=n;i++)  
                f[i][j]=f[f[i][j-1]][j-1];
    	while(q--)
    	{
    		scanf("%d%d",&x,&y);
    		if(l[x]>l[y])swap(x,y);
    		if(!mp[x][y])mp[x][y]=1,v=1;
    		else mp[x][y]=0,v=-1;
    		///根据所连边分情况讨论 画个草图就明白了
    		if(r[x]>=r[y])
    		{
    			int Y=y;
    			///倍增找到深度较小的点(x)的下一个点
    			for(int j=19;j>=0;j--)
                    if(dep[f[Y][j]]>dep[x]) 
                        Y=f[Y][j];
    			up(1,1,n,l[Y],l[y]-1,v),up(1,1,n,r[y]+1,r[Y],v);
    		}
    		else
    		up(1,1,n,1,l[x]-1,v),up(1,1,n,r[x]+1,l[y]-1,v),up(1,1,n,r[y]+1,n,v);
    		printf("%d\n",n-sum[1]);
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Njc3VfY2F0_size_16_color_FFFFFF_t_70]: /images/20220123/36cc4a0fff1a4a478fbd64f98349c1a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Njc3VfY2F0_size_16_color_FFFFFF_t_70 1]: /images/20220123/4006f332ee2a4a19969cd6c32f6bceea.png
[https_blog.csdn.net_ccsu_cat_article_details_83892646]: https://blog.csdn.net/ccsu_cat/article/details/83892646