对题意的转化其实挺巧妙的。
可以看出来是在树上再加“附加边”，加了附加边的即形成环。形成环的定要删除一条主要边和一条附加边才能分为两部分。
如添加了附加边（x，y），相当于x到y的所有“主要边”被覆盖一次。
若第一步把被覆盖0次的主要边切断，第二步可任意切断一条附加边。
若第一步把被覆盖1次的主要边切断，第二步可切断的附加边唯一。
若第一步把被覆盖2次及以上的主要边切断，第二步无论切断哪一条附加边都不能分成两部分。
转化为区间修改，单点查询，显然差分思想，只不过是在树上，所以与lca有关（用这道题来复习一下lca）
最后只要枚举每一条边看被覆盖几次，这里我们用一个数组cha[i]表示i上面的那条边被覆盖的次数
（点表示对应的边也是很重要的思想）
cha[a]++;cha[b]++;cha[LCA(a,b)]-=2;
#include <iostream> #include <cstdio> #include <cstring> #define N 100003 using namespace std; struct EDGE{ int nextt,to; }w[N*2]; int head[N],dep[N],f[N][22],cha[N]; int tot=0; int read() { int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } void dfs1(int x) { for(int i=head[x];i;i=w[i].nextt) { int y=w[i].to; if(y==f[x][0])continue; f[y][0]=x; dep[y]=dep[x]+1; for(int i=1;i<20;++i)f[y][i]=f[f[y][i-1]][i-1]; dfs1(y); } } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=19;i>=0;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y)return x; for(int i=19;i>=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } void dfs2(int x) { for(int i=head[x];i;i=w[i].nextt) { int y=w[i].to; if(y==f[x][0])continue; dfs2(y); cha[x]+=cha[y]; } } int main() { int n=read(),m=read(); for(int i=1;i<n;++i) { int a=read(),b=read(); add(a,b);add(b,a); } dfs1(1); for(int i=1;i<=m;++i) { int a=read(),b=read(); cha[a]++;cha[b]++; cha[LCA(a,b)]-=2; } dfs2(1); int ans=0; for(int i=2;i<=n;++i) { if(cha[i]==1)ans++; if(cha[i]==0)ans+=m; } printf("%d ",ans); }
复健真的好痛苦（枯了）