树上边的差分,给每个点赋值为0,对于非树边(x,y)x,y权值+1,lca(x,y)-=2,再dfs
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define MN 200050 using namespace std; int n,m,cnt,head[MN],ans[MN],dfn[MN],num[MN]; int f[MN][21]; int lg[MN]; struct tu{ int v,nxt; }e[MN]; void add(int u,int v){ e[++cnt].v=v; e[cnt].nxt=head[u]; head[u]=cnt; } void dfs(int now,int fa){ dfn[now]=dfn[fa]+1; f[now][0]=fa; for(int i=1;(1<<i)<=dfn[now];i++) f[now][i]=f[f[now][i-1]][i-1]; for(int i=head[now];i;i=e[i].nxt){ if(e[i].v!=fa)dfs(e[i].v,now); } } int lca(int x,int y){ if(dfn[x]<dfn[y])swap(x,y); while(dfn[x]>dfn[y]){ x=f[x][lg[dfn[x]-dfn[y]]]; } if(x==y)return x; for(int k=lg[dfn[x]];k>=0;k--) if(f[x][k]!=f[y][k]) x=f[x][k],y=f[y][k]; return f[x][0]; } void search(int now,int fa){ ans[now]=num[now]; for(int i=head[now];i;i=e[i].nxt){ if(e[i].v!=fa){ search(e[i].v,now); ans[now]+=ans[e[i].v]; //前缀和所以加儿子权 } } } int main(){ int sum=0; scanf("%d%d",&n,&m); lg[0]=-1; for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n-1;i++){ int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(1,0); for(int i=1;i<=m;i++){ int a,b; scanf("%d%d",&a,&b); num[a]++;num[b]++;num[lca(a,b)]-=2; } search(1,0); for(int i=2;i<=n;i++){ if(!ans[i])sum+=m; if(ans[i]==1)sum++; } printf("%d",sum); return 0; }
若有错误请指出