2018 icpc 徐州现场赛G-树上差分+组合数学-大佬的代码

现场赛大佬打印的代码，观摩了一哈。
写了注释，贴一下，好好学习。%%%PKU
代码：
  1 //树上差分(LCA)
  2 #include<bits/stdc++.h>
  3 
  4 #define For(i,x,y) for (int i=x;i<y;i++)
  5 #define fi first
  6 #define se second
  7 #define pb push_back
  8 #define mp make_pair
  9 #define lf else if
 10 
 11 #define dprintf(...) fprintf(stderr,__VA_ARGS__)
 12 using namespace std;
 13 
 14 typedef long long ll;
 15 typedef double db;
 16 typedef pair<int,int> pii;
 17 typedef vector<int> Vi;
 18 
 19 int IN(){//读入挂
 20     int c,f,x;
 21     while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
 22     while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
 23 }
 24 
 25 const int p=1e9+7;
 26 const int N=3e5+19;
 27 
 28 int Pow(int a,int b){//快速幂
 29     int res=1;
 30     for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
 31     return res;
 32 }
 33 
 34 struct Edge{
 35     int y,nxt;
 36 } E[N*2];
 37 int fac[N],inv[N];
 38 int las[N],fa[20][N],A[N],B[N],dep[N];
 39 int n,m,cnt,x,y,z,ans,k;
 40 
 41 int C(int n,int m){//组合数
 42     if (n<m) return 0;
 43     return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;
 44 }
 45 
 46 void Link(int x,int y){//链式前向星存图
 47     E[cnt]=(Edge){y,las[x]};las[x]=cnt++;
 48     E[cnt]=(Edge){x,las[y]};las[y]=cnt++;
 49 }
 50 
 51 void dfs(int x){//LCA的dfs
 52     for (int i=las[x],y;~i;i=E[i].nxt)
 53         if ((y=E[i].y)!=fa[0][x]){
 54             fa[0][y]=x;
 55             dep[y]=dep[x]+1;
 56             dfs(y);
 57         }
 58 }
 59 
 60 int LCA(int x,int y){//LCA(ST)
 61     if (dep[x]>dep[y]) swap(x,y);
 62     for (int i=dep[y]-dep[x],k=0;i;i>>=1,k++) if(i&1) y=fa[k][y];
 63     if(x==y) return x;
 64     for (int i=19;~i;i--) if (fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
 65     return fa[0][x];
 66 }
 67 
 68 void Dfs(int x){//树上差分的dfs，从根节点深搜，回溯时将其本身的权值加上所有子节点的权值
 69     for (int i=las[x],y;~i;i=E[i].nxt)
 70         if ((y=E[i].y)!=fa[0][x]){//筛掉父节点
 71             Dfs(y);
 72             A[x]+=A[y];//累加权值和
 73             B[x]+=B[y];
 74         }
 75 }
 76 
 77 void Main(){
 78     n=IN(),m=IN(),k=IN();
 79     For(i,1,n+1) las[i]=-1,A[i]=B[i]=0;
 80     cnt=0;
 81     For(i,1,n) Link(IN(),IN());
 82     dfs(1);
 83     For(i,1,20) For(x,1,n+1) fa[i][x]=fa[i-1][fa[i-1][x]];
 84     For(i,1,m+1){
 85         x=IN(),y=IN();
 86         z=LCA(x,y);
 87         A[x]++,A[y]++,A[z]--,A[fa[0][z]]--;
 88         B[x]++,B[y]++,B[z]-=2;//起点终点权值+1，lca权值-2
 89     }
 90     Dfs(1);
 91     ans=0;
 92 //    cout<<"--------"<<endl;
 93 //    for(int i=1;i<=n;i++)
 94 //        cout<<i<<" "<<A[i]<<endl;
 95 //    cout<<"--------"<<endl;
 96 //    for(int i=2;i<=n;i++)
 97 //        cout<<i<<" "<<B[i]<<endl;
 98 //    cout<<"--------"<<endl;
 99     For(i,1,n+1){
100         ans=(ans+C(A[i],k))%p;
101     }
102     For(i,2,n+1){
103         ans=(ans-C(B[i],k)+p)%p;
104     }
105     printf("%d
",ans);
106 }
107 
108 int main(){
109     fac[0]=1;
110     For(i,1,N) fac[i]=1ll*fac[i-1]*i%p;
111     inv[N-1]=Pow(fac[N-1],p-2);
112     for(int i=N-1;i;i--) inv[i-1]=1ll*inv[i]*i%p;
113     for(int T=IN();T--;) Main();
114 }
115 
116 /*
117 1
118 3 6 2
119 1 2
120 1 3
121 1 1
122 2 2
123 3 3
124 1 2
125 1 3
126 2 3
127 */
OK.