关于lca和树上差分的题目。
根据题目描述，主要边是一棵树，附加边会和主要边构成一个环，如果我们第一步切断了一条主要边，我们下一步就必须切断一条附加边才能符合题意。
所以，我们可以认为一条附加边(x,y)把树上x,y之间的路径覆盖了一遍，我们需要统计每条主要边被覆盖多少次即可。具体地，如果第一步我们切断被覆盖0次的边（这条边上没有附加边，切断一次就已经不连通了），那么我们第二次可以切断m条附加边的任意一条。如果我们切断覆盖一次的边，那么我们第二次的方法唯一确定。如果我们第一步切断被覆盖2次或以上的边，那么我们无论如何也无法切断整个图。这样我们就得到了答案。
我们使用树上差分来解决。对于每一条附加边(x,y)，我们将x，y的权值分别加1，将lca(x,y)的权值-2，之后我们遍历一遍这棵树，设tot[x]表示以x为根的子树的权值之和，那么f[x]就是x与他的父亲的路径被覆盖的次数。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 inline int read() { 8 ????int ret=0; 9 ????int op=1;10 ????char c=getchar();11 ????while(c<‘0‘||c>‘9‘) {if(c==‘-‘) op=-1; c=getchar();}12 ????while(c<=‘9‘&&c>=‘0‘) ret=ret*10+c-‘0‘,c=getchar();13 ????return ret*op;14 }15 struct node {16 ????int next,to;17 }a[100010<<1];18 int num,head[100010<<1];19 int n,m,tot[100010],fa[100010][25],d[100010];20 inline void add(int from,int to) {21 ????a[++num].next=head[from];22 ????a[num].to=to;23 ????head[from]=num;24 }25 void dfs(int u,int f) {26 ????d[u]=d[f]+1;27 ????fa[u][0]=f;28 ????for(int i=0;i<20;i++)29 ????????fa[u][i+1]=fa[fa[u][i]][i];30 ????for(int i=head[u];i;i=a[i].next) {31 ????????int v=a[i].to;32 ????????if(v==f) continue ;33 ????????dfs(v,u);34 ????}35 }36 int lca(int x,int y) {37 ????if(d[x]<d[y]) swap(x,y);38 ????for(int i=20;i>=0;i--) {39 ????????if(d[fa[x][i]]>=d[y]) x=fa[x][i];40 ????????if(x==y) return x;41 ????}42 ????for(int i=20;i>=0;i--) {43 ????????if(fa[x][i]!=fa[y][i]) {44 ????????????x=fa[x][i];45 ????????????y=fa[y][i];46 ????????}47 ????}48 ????return fa[x][0];49 }50 int calc(int u,int f) {51 ????for(int i=head[u];i;i=a[i].next) {52 ????????int v=a[i].to;53 ????????if(v==f) continue ;54 ????????tot[u]+=calc(v,u);55 ????}56 ????return tot[u];57 }58 int main() {59 ????n=read(); m=read();60 ????for(int i=1;i<n;i++) {61 ????????int x=read(),y=read();62 ????????add(x,y);63 ????????add(y,x);64 ????}65 ????dfs(1,0);66 ????for(int i=1;i<=m;i++) {67 ????????int x=read(),y=read();68 ????????tot[x]++;69 ????????tot[y]++;70 ????????tot[lca(x,y)]-=2;71 ????}72 ????calc(1,0);73 ????int ans=0;74 ????for(int i=1;i<=n;i++) {75 ????????if(tot[i]==0&&i!=1) ans+=m;76 ????????if(tot[i]==1) ans++;77 ????}78 ????printf("%d\n",ans);79 ????return 0;80 }【POJ3417】Network
原文地址：https://www.cnblogs.com/shl-blog/p/10800522.html