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

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

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e5+;

 struct thxorz{int to,nxt;}G[N<<],G2[N<<];

 int Head[N],Head2[N],tot,tot2;

 int n,m,ans;

 inline void Addedge(int x,int y){

     G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot;

     G[++tot].to=x,G[tot].nxt=Head[y],Head[y]=tot;

 }

 inline void Addedge2(int x,int y){

     G2[++tot2].to=y,G2[tot2].nxt=Head2[x],Head2[x]=tot2;

     G2[++tot2].to=x,G2[tot2].nxt=Head2[y],Head2[y]=tot2;

 }

 #define lowbit(x) x&(-x)

 int C[N];

 inline void Add(int x){for(;x<=n;x+=lowbit(x))++C[x];}

 inline int Sum(int x){int ret=;for(;x;x-=lowbit(x))ret+=C[x];return ret;}

 int st[N],ed[N],tim;

 #define y G[j].to

 void dfs(int x,int fa){

     st[x]=++tim;

     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa)dfs(y,x);

     ed[x]=tim;

 }

 void calc(int x,int fa){

     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa){

         int tmp=Sum(n)-(Sum(ed[y])-Sum(st[y]-));

         calc(y,x);

         tmp=Sum(n)-(Sum(ed[y])-Sum(st[y]-))-tmp;

         ans+=tmp?tmp==:m;

     }

     for(register int j=Head2[x];j;j=G2[j].nxt)Add(st[G2[j].to]);

 }

 #undef y

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n),read(m);

     for(register int i=,x,y;i<n;++i)read(x),read(y),Addedge(x,y);

     for(register int i=,x,y;i<=m;++i)read(x),read(y),Addedge2(x,y);

     dfs(,);calc(,);

     return printf("%d\n",ans),;

 }

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

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

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

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

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

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

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

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

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

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

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e5+;

 struct thxorz{int to,nxt;}G[N<<],Q[N<<];

 int Head[N],qh[N],tot,qtot;

 inline void Addedge(int x,int y){

     G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot;

     G[++tot].to=x,G[tot].nxt=Head[y],Head[y]=tot;

 }

 inline void Addquery(int x,int y){

     Q[++qtot].to=y,Q[qtot].nxt=qh[x],qh[x]=qtot;

     if(x^y)Q[++qtot].to=x,Q[qtot].nxt=qh[y],qh[y]=qtot;

 }

 int anc[N],vis[N],d[N];

 int n,m,ans;

 int ancestor(int x){return anc[x]==x?x:anc[x]=ancestor(anc[x]);}

 #define y G[j].to

 #define qy Q[j].to

 void tarjan(int x,int fa){

     anc[x]=x;

     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa)tarjan(y,x),anc[y]=x;

     vis[x]=;

     for(register int j=qh[x];j;j=Q[j].nxt)if(vis[qy])d[ancestor(qy)]-=;

 }

 int dfs(int x,int fa){

     int tmp=d[x];

     for(register int j=Head[x];j;j=G[j].nxt)if(y^fa)tmp+=dfs(y,x);

     if(x^)ans+=tmp?tmp==:m;

     return tmp;

 }

 #undef qy

 #undef y

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n),read(m);

     for(register int i=,x,y;i<n;++i)read(x),read(y),Addedge(x,y);

     for(register int i=,x,y;i<=m;++i)read(x),read(y),Addquery(x,y),++d[x],++d[y];

     tarjan(,);dfs(,);

     return printf("%d\n",ans),;

 }

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

巴特西

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

最新文章

热门文章