poj3417 Network/闇の連鎖[树上差分]

首先隔断一条树边，不计附加边这个树肯定是断成两块了，然后就看附加边有没有连着的两个点在不同的块内。

方法1：BIT乱搞（个人思路）

假设考虑到$x$节点隔断和他父亲的边，要看$x$子树内有没有点连着附加边到子树外的。如果没有，则随便割，有1个，有唯一割法，否则没有。这个可以用dfs序处理好序列后，直接将与一个点附加边牵连的另一个点在BIT里+1，类似晋升者计数那题一样的思路用BIT求答案。$O(mlogn)$。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define dbg(x) cerr << #x << " = " << x <<endl
 7 using namespace std;
 8 typedef long long ll;
 9 typedef double db;
10 typedef pair<int,int> pii;
11 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
12 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
13 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
14 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
15 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
16 template<typename T>inline T read(T&x){
17     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
18     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
19 }
20 const int N=1e5+7;
21 struct thxorz{int to,nxt;}G[N<<1],G2[N<<1];
22 int Head[N],Head2[N],tot,tot2;
23 int n,m,ans;
24 inline void Addedge(int x,int y){
25     G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot;
26     G[++tot].to=x,G[tot].nxt=Head[y],Head[y]=tot;
27 }
28 inline void Addedge2(int x,int y){
29     G2[++tot2].to=y,G2[tot2].nxt=Head2[x],Head2[x]=tot2;
30     G2[++tot2].to=x,G2[tot2].nxt=Head2[y],Head2[y]=tot2;
31 }
32 #define lowbit(x) x&(-x)
33 int C[N];
34 inline void Add(int x){for(;x<=n;x+=lowbit(x))++C[x];}
35 inline int Sum(int x){int ret=0;for(;x;x-=lowbit(x))ret+=C[x];return ret;}
36 int st[N],ed[N],tim;
37 #define y G[j].to
38 void dfs(int x,int fa){
39     st[x]=++tim;
40     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa)dfs(y,x);
41     ed[x]=tim;
42 }
43 void calc(int x,int fa){
44     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa){
45         int tmp=Sum(n)-(Sum(ed[y])-Sum(st[y]-1));
46         calc(y,x);
47         tmp=Sum(n)-(Sum(ed[y])-Sum(st[y]-1))-tmp;
48         ans+=tmp?tmp==1:m;
49     }
50     for(register int j=Head2[x];j;j=G2[j].nxt)Add(st[G2[j].to]);
51 }
52 #undef y
53 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
54     read(n),read(m);
55     for(register int i=1,x,y;i<n;++i)read(x),read(y),Addedge(x,y);
56     for(register int i=1,x,y;i<=m;++i)read(x),read(y),Addedge2(x,y);
57     dfs(1,0);calc(1,0);
58     return printf("%d
",ans),0;
59 }

View Code

方法2：树上差分（思路纠正）

当割掉的树边两端有点通过附加边牵连时，附加边对应的两个点形成的链经过这个割边，很容易想。

那么反过来说，每对附加边的点对$x,y$这条链上的边都加上1，相当于这个割边两端的牵连点的对数。

于是这个是树上差分裸题。改链求边。

以前学的树上差分姿势不对，今天重学了一遍。。然后发现网上到处都说这种链差分只要$d_x++,d_y++,d_{lca(x,y)}-=2$，基本没有人说这是为什么。

我自己看了好久没看懂为什么这么做是对的，一气之下自己试着将差分原理搬到树上得知了正确性。你们好多人根本没有懂树上差分的精髓！！

抱歉，上面那句有点狂了，但确实，很多人都没想过树上差分数组$d_i$表示什么？操作为什么是对的？换一种形式还可以改造吗？

差分数组里，$d_i=A_i-A_{i-1}$，而$sumlimits_{j=1}^{i}d_j=A_i$，类似的，设在树上，若$A_x$是节点$x$与父亲的连边，则$d_x=A_x-sumlimits_{yin son}A_y$，这样，$sumlimits_{yin 子树x}d_y=A_x$，也就是说，把子树内所有点的$d$加起来就是这个边的值。

于是，修改一条链，拆成修改$x o lca$和$lca o y$，$x$到$lca$这个链统一加上一个值，中间的$d_i$差值不变，而$d_x$要加上这个值，$d_{lca}$相应减去这个值，为什么这样，应该就不难理解了，保证了差值的正确性，使得子树和可以正确表示。

这样，如果树边有初始值，也可以通过做差的形式直接构造出这个树上差分数组。

然后再来看题，这里是相当于所有修改操作都做完了，最后统一询问。如果强制在线，应当还是要dfs序做完之后用数据结构维护子树的差分数组之和。但这题可以离线，加上tarjanLCA于是O(n)解决。

另外，同样，点差分也可以通过类似的思路来维护，只是将$lca$稍作修改即可($d_{lca}-=val,d_{fa_{lca}}-=val$)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define dbg(x) cerr << #x << " = " << x <<endl
 7 using namespace std;
 8 typedef long long ll;
 9 typedef double db;
10 typedef pair<int,int> pii;
11 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
12 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
13 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
14 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
15 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
16 template<typename T>inline T read(T&x){
17     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
18     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
19 }
20 const int N=1e5+7;
21 struct thxorz{int to,nxt;}G[N<<1],Q[N<<1];
22 int Head[N],qh[N],tot,qtot;
23 inline void Addedge(int x,int y){
24     G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot;
25     G[++tot].to=x,G[tot].nxt=Head[y],Head[y]=tot;
26 }
27 inline void Addquery(int x,int y){
28     Q[++qtot].to=y,Q[qtot].nxt=qh[x],qh[x]=qtot;
29     if(x^y)Q[++qtot].to=x,Q[qtot].nxt=qh[y],qh[y]=qtot;
30 }
31 int anc[N],vis[N],d[N];
32 int n,m,ans;
33 int ancestor(int x){return anc[x]==x?x:anc[x]=ancestor(anc[x]);}
34 #define y G[j].to
35 #define qy Q[j].to
36 void tarjan(int x,int fa){
37     anc[x]=x;
38     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa)tarjan(y,x),anc[y]=x;
39     vis[x]=1;
40     for(register int j=qh[x];j;j=Q[j].nxt)if(vis[qy])d[ancestor(qy)]-=2;
41 }
42 int dfs(int x,int fa){
43     int tmp=d[x];
44     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa)tmp+=dfs(y,x);
45     if(x^1)ans+=tmp?tmp==1:m;
46     return tmp;
47 }
48 #undef qy
49 #undef y
50 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
51     read(n),read(m);
52     for(register int i=1,x,y;i<n;++i)read(x),read(y),Addedge(x,y);
53     for(register int i=1,x,y;i<=m;++i)read(x),read(y),Addquery(x,y),++d[x],++d[y];
54     tarjan(1,0);dfs(1,0);
55     return printf("%d
",ans),0;
56 }

View Code

最后是非常蠢的一些错误记录：法1里面加边打错了。。该打。。。法2里面原来我tarjan求lca姿势一直是错的TuT，如果询问两个相同点就会GG，所以应当提前将vis置为1，然后查点对询问。