部落冲突

题目背景

在一个叫做Travian的世界里，生活着各个大大小小的部落。其中最为强大的是罗马、高卢和日耳曼。他们之间为了争夺资源和土地，进行了无数次的战斗。期间诞生了众多家喻户晓的英雄人物，也留下了许多可歌可泣的动人故事。

其中，在大大小小的部落之间，会有一些道路相连，这些道路是Travian世界里的重要枢纽，简单起见，你可以把这些部落与部落之间相连的道路看作一颗树，可见每条道路对于Travian世界的重要程度。有了这些道路，建筑工人就可以通过这些道路进行友好外交啦。

然而，事情并不会像想象的那样美好，由于资源的匮乏，相邻的部落（由一条道路相连的部落）之间经常会发生大大小小的冲突事件，更有甚者，会升级为部落之间的大型战争。

为了避免误伤，每当两个相邻的部落之间发生大型战争之时，这两个部落间的道路是不允许通行的，对于一些强大的部落，甚至能与多个相邻的部落同时开战，同样的，这些战争地带的道路十分危险，是不可通行的。

天下之势，分久必合，当两个部落经历了不打不相识的苦战之后，他们可以签订停战协议（暂时停战，以后依旧可能再次开战），这样，两个部落之间的道路又会重新恢复为可通行状态，建筑工人们又可以经过此地购买最新的大本营设计图纸来强大自己的部落了。

为了简单起见，我们把各大战争事件按发起的时间顺序依次编号（最先发起的战争编号就为 1，第二次战争编号就为 2，以此类推），当两个部落停战之时，则会直接告诉你这场战争的编号，然后这场战争就载入了史册，不复存在了，当然，这并不会影响到其他战争的编号。

建筑工人十分讨厌战争，因为战争，想从一个部落到另一个部落进行友好交流的建筑工人可能就此白跑一趟。所以，在他们出发之前，都会向你问问能不能到达他们想去的部落。

题目描述

简单起见，你就是要处理下面三件事，所有的事件都是按照时间顺序给出的。

1.（Q p q) 从第 p 个部落出发的建筑工人想知道能否到达第q个部落了，你要回答的便是（Yes/No），注意大小写

2.（C p q) 第 p个部落与第 q个部落开战了，保证他们一定是相邻的部落，且目前处于停战（未开战）状态

3.（U x ）第 x次发生的战争结束了，它将永远的被载入史册，不复存在（保证这个消息不会告诉你多次）

输入输出格式

输入格式：

第一行两个数 n 和 m，n 代表了一共有 n 个部落，m 代表了以上三种事件发生的总数

接下来的 n−1行，每行两个数 p , q，代表了第 p 个部落与第 q 个部落之间有一条道路相连

接下来的 m 行，每行表示一件事，详见题目描述

输出格式：

每行一个“Yes”或者“No”，表示从第 p 个部落出发的建筑工人能否到达第 q 个部落

输出格式：

每行一个“

输入输出样例

输入样例#1：

输出样例#1：

Yes
No
No
No

样例#2：

10 10
1 2
1 3
3 4
3 5
1 6
3 7
1 8
2 9
5 10
C 8 1
Q 6 1
C 2 1
Q 2 10
U 1
C 9 2
C 7 3
U 3
Q 6 7
Q 1 10
---------------
Yes
No
No
Yes

View

样例#3：

View

说明

对于30%的数据 1<=n，m<=6000

对于另30%的数据，保证部落之间的地理关系是一条链，且 i 与 i + 1 之间有一条道路

对于另30%的数据，1<=n，m<=100000

对于100%的数据，1<=n，m<=300000

思路

这道题，一看这不是裸的链剖题吗？对于两个开战的点之间+1，查询的话两个点之间就看是不是和为0，消除战争就-1，用线段树维护

然后我就完美的T了一个点（我在本地跑最慢的点0.484s,洛谷上T了！！！）

然后这道题正解是树上差分，对于两个开战的 u , v 点必定相邻，设dep[u]>dep[v]则产生干扰的是从u的子树到非v的子树，

那么我们就可以记录一个dfs序，在u的入度-1，u的出度+1，查询两点x，y时验证x的dfs序前缀和+y的dfs序前缀和-2×lca(x,y)的dfs序前缀和等不等于x，y之间点的个数(dep[x]+dep[y]-2×lca(x,y))即可

  1 /***************************************************
  2  * 查询两点是否连通，相当于查询两点之间是否有断点
  3  * 那么考虑树上差分，维护每个点到根节点的路径上，断点
  4  * 的个数，直接按照DFS序，用树状数组维护即可
  5  **************************************************/
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <vector>
  9 using namespace std;
 10 const int maxn = 300300;
 11 const int maxm = 300300;
 12 int n, m, tot, coc, root;
 13 vector <int> G[ maxn ];
 14 struct BIT{
 15     int s[ maxn << 1 ];
 16     void add(int p,int v){
 17         for(int i = p ; i <= n << 1 ; i += i & (-i) )
 18             s[ i ] += v;
 19     }
 20     int query(int p){
 21         int rtn = 0;
 22         for(int i = p ; i ; i -= i & (-i) )
 23             rtn += s[ i ];
 24         return rtn;
 25     }
 26 }dis;
 27 
 28 int dep[ maxn ], son[ maxn ], fa[ maxn ], sz[ maxn ], top[ maxn ], pin[ maxn ], pout[ maxn ];
 29 int Q[ maxm ];
 30 void dfs1(int k){
 31     sz[ k ] = 1;
 32     for(int i = 0; i < G[ k ].size(); ++i){
 33         int kk = G[ k ][ i ];
 34         if( kk == fa[ k ] ) continue;
 35         fa[ kk ] = k;
 36         dep[ kk ] = dep[ k ] + 1;
 37         dfs1( kk );
 38         if( sz[ son[ k ] ] < sz[ kk ] ) son[ k ] = kk;
 39         sz[ k ] += sz[ kk ];
 40     }
 41 }
 42 void dfs2(int k, int t){
 43     top[ k ] = t;
 44     pin[ k ] = ++coc;
 45     if( !son[ k ] ) return ( void ) (pout[ k ] = ++coc);
 46     dfs2( son[k] , t );
 47     for(int i = 0; i < G[ k ].size(); ++i){
 48         int kk = G[ k ][ i ];
 49         if( kk == fa[ k ] || kk == son[ k ] )continue;
 50         dfs2( kk , kk );
 51     }
 52     return ( void ) (pout[ k ] = ++coc);
 53 }
 54 int lca(int x, int y){
 55     while( top[ x ] != top[ y ] ){
 56         if( dep[ top[ x ] ] < dep[ top[ y ] ] ) swap(x, y);
 57         x = fa[ top[ x ] ];
 58     }return dep[ x ] < dep[ y ] ? x : y;
 59 }/*
 60 struct io {
 61     char op[ 1 << 25 ] , *s;
 62     io(){
 63         //freopen("lct.in", "r", stdin);
 64         //freopen("lct.out", "w", stdout);
 65         fread( s = op , 1 , 1 << 25 , stdin );
 66     }  
 67     int read(){
 68         int u = 0;
 69         while( *s < 48 || *s > 57 )s++;
 70         while( *s > 47 && *s < 58 )u = ( u << 1 ) + ( u << 3 ) + *s++ - 48;
 71         return u;
 72     }
 73     char gc(){
 74         while( *s < 'A' || *s > 'Z' )s++;
 75         return *s++ ;
 76     }
 77 }ip;
 78 #define read ip.read
 79 #define gcha ip.gc*/
 80 
 81 inline int read()
 82 {
 83     int x=0,f=1;char c=getchar();
 84     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 85     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 86     return x*f;
 87 }
 88 
 89 int main(){
 90     
 91     n = read(); m = read();
 92     for(int i = 1; i < n; ++i){
 93         int x = read() , y = read();
 94         G[ x ].push_back( y );
 95         G[ y ].push_back( x );
 96     }
 97     root = n / 2;
 98     dfs1( root );
 99     dfs2( root , root );
100     for(int i = 1; i <= n; ++i){
101         dis.add( pin[ i ], 1 );
102         dis.add( pout[ i ],-1 );
103     }
104     while( m-- ){
105         char s[5];
106         int  p, q, l, D1, D2;
107         scanf("%s",s);
108         switch( s[ 0 ] ){
109             case 'Q':    p = read(); q = read();
110                         l = lca( p , q );
111                         D1 = dep[ p ] + dep[ q ] - 2 * dep[ l ];
112                         D2 = dis.query( pin[ p ] ) + dis.query( pin[ q ] ) - 2 * dis.query( pin[ l ] );
113                         if(D1 == D2) printf("Yes
"); else printf("No
"); break;
114             case 'C':    p = read(); q = read();
115                         if(dep[ p ] < dep[ q ]) p = q;
116                         Q[ ++tot ] = p;
117                         dis.add( pin[ p ], -1 );
118                         dis.add( pout[ p ], 1 );
119                         break;
120             case 'U':    p = read();
121                         p = Q[ p ];
122                         dis.add( pin[ p ], 1 );
123                         dis.add( pout[ p ], -1 );
124                         break;
125         }
126     }
127     return 0;
128 }

AC Code

  1 #include<set>
  2 #include<map>
  3 #include<queue>
  4 #include<stack>
  5 #include<cstdio>
  6 #include<cstring>
  7 #include<iostream>
  8 #include<algorithm>
  9 #define inf (1<<30)
 10 #define ll long long
 11 #define RG register int
 12 #define rep(i,a,b)    for(RG i=a;i<=b;i++)
 13 #define per(i,a,b)    for(RG i=a;i>=b;i--)
 14 #define ls (pos<<1)
 15 #define rs (pos<<1|1)
 16 #define add(u,v) (e[++cnt].v=v,e[cnt].next=head[u],head[u]=cnt,swap(u,v),e[++cnt].v=v,e[cnt].next=head[u],head[u]=cnt)
 17 #define mid ((L+R)>>1)
 18 #define maxn 300005
 19 using namespace std;
 20 int n,m,cnt,qc,id;
 21 int head[maxn],rec[maxn][2];
 22 int son[maxn],sz[maxn],fa[maxn],dep[maxn],dfn[maxn],node[maxn],top[maxn];
 23 struct E{
 24     int v,next;
 25 }e[maxn<<1];
 26 struct T{
 27     int sum,lazy;
 28 }t[maxn<<2];
 29 
 30 inline int read()
 31 {
 32     int x=0,f=1;char c=getchar();
 33     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 34     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 35     return x*f;
 36 }
 37 
 38 void dfs1(int u,int pa)
 39 {
 40     sz[u]=1,fa[u]=pa,dep[u]=dep[pa]+1;
 41     for(int i=head[u];i;i=e[i].next)
 42     {
 43         int v=e[i].v;
 44         if(v==pa)    continue;
 45         dfs1(v,u);
 46         sz[u]+=sz[v];
 47         if(sz[v]>sz[son[u]])    son[u]=v;
 48     }
 49 }
 50 
 51 void dfs2(int u,int tp)
 52 {
 53     dfn[u]=++id,node[id]=u,top[u]=tp;
 54     if(!son[u])    return;
 55     dfs2(son[u],tp);
 56     for(int i=head[u];i;i=e[i].next)
 57         if(e[i].v!=fa[u]&&e[i].v!=son[u])dfs2(e[i].v,e[i].v);
 58 }
 59 
 60 
 61 int query(int pos,int l,int r,int L,int R)
 62 {
 63     if(l<=L&&R<=r)    return t[pos].sum;
 64     int len=R-L+1;
 65     if(t[pos].lazy)
 66     {
 67         t[ls].sum+=t[pos].lazy*(len-(len>>1));
 68         t[rs].sum+=t[pos].lazy*(len>>1);
 69         t[ls].lazy+=t[pos].lazy,t[rs].lazy+=t[pos].lazy;
 70         t[pos].lazy=0;
 71     }
 72     int sum=0;
 73     if(l<=mid)    sum+=query(ls,l,r,L,mid);
 74     if(r>mid)    sum+=query(rs,l,r,mid+1,R);
 75     return sum;
 76 }
 77 
 78 void update(int pos,int l,int r,int L,int R,int val)
 79 {
 80     if(l<=L&&R<=r)
 81     {
 82         t[pos].lazy=val,t[pos].sum+=(R-L+1)*val;return;
 83     }
 84     int len=R-L+1;
 85     if(t[pos].lazy)
 86     {
 87         t[ls].sum+=t[pos].lazy*(len-(len>>1));
 88         t[rs].sum+=t[pos].lazy*(len>>1);
 89         t[ls].lazy+=t[pos].lazy,t[rs].lazy+=t[pos].lazy;
 90         t[pos].lazy=0;
 91     }
 92     if(l<=mid)update(ls,l,r,L,mid,val);
 93     if(r>mid) update(rs,l,r,mid+1,R,val);
 94     t[pos].sum=t[ls].sum+t[rs].sum;
 95 }
 96 
 97 bool ask(int x,int y)
 98 {
 99     int sum=0;
100     while(top[x]!=top[y])
101     {
102         if(dep[top[x]]<dep[top[y]])    swap(x,y);
103         sum=query(1,dfn[top[x]],dfn[x],1,n);
104         if(sum)    return 0;
105         x=fa[top[x]];
106     }
107     if(x==y)    return 1;
108     if(dep[x]>dep[y])    swap(x,y);
109     sum=query(1,dfn[x]+1,dfn[y],1,n);
110     if(sum)        return 0;return 1;
111 }
112 
113 void change(int x,int y,int val)
114 {
115     while(top[x]!=top[y])
116     {
117         if(dep[top[x]]<dep[top[y]])    swap(x,y);
118         update(1,dfn[top[x]],dfn[x],1,n,val);
119         x=fa[top[x]];
120     }
121     if(x==y)    return;
122     if(dep[x]>dep[y])    swap(x,y);
123     update(1,dfn[x]+1,dfn[y],1,n,val);
124     return;
125 }
126 
127 int main()
128 {
129     char s[5];int a,b;
130     n=read(),m=read();
131     for(RG i=1,u,v;i<n;i++)    u=read(),v=read(),add(u,v);
132     dfs1(1,0);
133     dfs2(1,0);
134     while(m--)
135     {
136         scanf("%s",s);
137         if(s[0]=='C')
138         {
139             a=read(),b=read();if(a>b)    swap(a,b);
140             rec[++qc][0]=a,rec[qc][1]=b;
141             change(a,b,1);
142         }
143         else if(s[0]=='Q')
144         {
145             a=read(),b=read();bool flg=ask(a,b);
146             if(flg)puts("Yes");
147             else   puts("No");
148         }
149         else
150         {
151             a=read();change(rec[a][0],rec[a][1],-1);
152         }
153     }
154     return 0;
155 }

链剖90分Code