原题链接
Description
传说中的暗之连锁被人们称为Dark。Dark是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。经过研究，你发现Dark呈现无向图的结构，图中有N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有N–1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有M条附加边。
你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断Dark的一条附加边。现在你想要知道，一共有多少种方案可以击败Dark。注意，就算你第一步切断主要边之后就已经把Dark斩为两截，你也需要切断一条附加边才算击败了Dark。
Input
第一行包含两个整数N和M。
之后N–1行，每行包括两个整数A和B，表示A和B之间有一条主要边。
之后M行以同样的格式给出附加边。
Output
输出一个整数表示答案。
Samples
Input 复制
4 1
1 2
2 3
1 4
3 4
Output
3
Hint
对于20%的数据，N≤100，M≤100。
对于100%的数据，N≤100000，M≤200000。数据保证答案不超过231–1。
题意：
给你n个点，n-1条主要边，以及m条附加边。
要求先删除主要边再删除附加边使得图不连通，问方案数。
思路：
考虑主要边删除后对图的影响，以及附加边和主要边的关系：
1.当主要边上没有附加边时，那么删除了该条主要边，再删除任意附加边，就会使得图不连通。
2.当主要边上只有一条附加边时，删除该条主要边后，还有条附加边连着，要想使得图不联通，只能删除该附加边，方案数有1种。
3.当主要边上的附加边条数大于等于2时，删除主要边后，无论删除哪一条附加边，图依旧联通，不合法。
最后dfs统计答案就可以了。
再看如何计算一条主要边被多少条附加边覆盖，附加边和主要边不一定重合，所以可以通过差分来维护，每次将端点的权值+1，再将LCA的权值-2.就相当于只将端点之间的值+1.
求LCA用的是bfs+倍增，由于是无向图，所以根节点的选择对答案不会产生影响。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) const double eps=1e-8; const int maxn=1e6+7; int h[maxn],idx; struct node{ int e,ne,w; }edge[maxn]; void add(int u,int v,int w){ edge[idx]={v,h[u],w};h[u]=idx++; } int n,m,a[maxn],res; ///int in[maxn]; int dep[maxn],fa[maxn][16]; void bfs(int u){ queue<int>q; memset(dep,0x3f,sizeof dep); dep[0]=0; dep[1]=1; q.push(1); while(!q.empty()){ int t=q.front();q.pop(); for(int i=h[t];~i;i=edge[i].ne){ int j=edge[i].e; if(dep[j]>dep[t]+1){ dep[j]=dep[t]+1; q.push(j); fa[j][0]=t; for(int k=1;k<=15;k++) fa[j][k]=fa[fa[j][k-1]][k-1]; } } } } int lca(int a,int b){ if(dep[a]<dep[b]) swap(a,b); for(int k=15;k>=0;k--) if(dep[fa[a][k]]>=dep[b]) a=fa[a][k];///使a,b跳到同一层 if(a==b) return a; for(int k=15;k>=0;k--) if(fa[a][k]!=fa[b][k]) a=fa[a][k],b=fa[b][k]; return fa[a][0]; } void update(int u,int v){ a[u]++;a[v]++;a[lca(u,v)]-=2; } void dfs(int u,int fa){ for(int i=h[u];~i;i=edge[i].ne){ int j=edge[i].e; if(j==fa) continue; dfs(j,u); a[u]+=a[j]; if(a[j]==0) res+=m; else if(a[j]==1) res+=1; } } int main() { n=read,m=read; memset(h,-1,sizeof h); for(int i=1;i<=n-1;i++){ int u=read,v=read; add(u,v,0);add(v,u,0); } bfs(1); rep(i,1,m){ int u=read,v=read; update(u,v); } dfs(1,-1); printf("%d\n",res); return 0; }
