问题描述

在的古老传说中，暗之连锁是人类内心黑暗的产物。人们又称它为 Dark。一代又一代 的武士们都试图打倒它，同时作为自然科学先驱 者和剑道高手的 ZYS也不例外。 ZYS发现，Dark 实际上可以抽象为由 N N 个 点、M+N−1 M+N−1 条边构成的无向图，图中的边分为两 类，分别称为主要边和附加边。其中 N–1 N–1 条为主 要边，M M 条为附加边，并且任意两点之间必定存在一条仅由主要边构成的简单 路径。 以 ZYS的能力，最多可以斩断 Dark 的一条主要边和一条附加边。最初， Dark 处于引诱模式，所有的附加边都处于无敌状态，但主要边可以被斩断。在 一条主要边被斩断后，Dark 立刻进入认真模式，剩余的主要边处于无敌状态， 而附加边可以被斩断。如果在斩断一条主要边和一条附加边后，构成 Dark 的 N N 个点被分成不连通的两部分，那么 Dark 会强制进入消减模式并最终灭亡。 ZYS想要知道，一共有多少种方案可以击败 Dark。注意，就算斩断一条 主要边之后，Dark 已经分为两截，你也需要再任意斩断一条附加边。

输入格式

第一行包含两个整数 N N 和 M M 。 之后 N–1 N–1 行，每行包括两个整数 A A 和 B B ，表示 A A 和 B B 之间有一条主要边。 之后 M M 行以同样的格式给出附加边。

输出格式

输出一个整数表示答案。

样例输入

4 1 1 2 2 3 1 4 3 4

样例输出

3

数据范围

对于 20% 20% 的数据，N≤100，M≤100 N≤100，M≤100 。

对于 100% 100% 的数据，N≤100000，M≤200000 N≤100000，M≤200000 。数据保证答案不超过 2 31 –1 231–1 。

时空限制

2S/512MB

题解

第一道树上差分。差分，就是在大都市meg里面学到的那种开头减，结尾加，前缀和来看状态的方法，例题还有一道借教室(不是换教室！)。在树上差分可以表示出两点之间的路径，只要在两端点均+1，LCA-2，最后用dfs统计和就可以了。过去学的LCA有朴素、ST、tarjan离线、在线、倍增，这次用的是tarjan，大概也是我最熟练的一种：两次头插法分别加双向边和存问题，还要用到并查集。差分、LCA、dfs三个步骤结束后得到每条实边被x条虚边覆盖，x=0的实边对答案有m的贡献，x=1的实边对答案有1的贡献。学长们出的加强版需要删掉不止一条虚边一条实边，如果边有富裕的话就会产生一个组合数的贡献，计算组合数大概是ad学长上次讲到的那些方法，数据小递推就可以了。

（摘自神犇moyiii“暗之链锁”题解）

1 #include
      
         2 using namespace std;  3 const int sj=200010;  4 int n,m,po[sj/2],a1,a2,jg,h[sj],l[sj],ans[sj],e,f;  5 int fa[sj/2],zx[sj/2],re[sj/2],dep[sj/2];  6 struct B{  7     int u,v,ne;  8 }b[sj];  9 struct Q{ 10     int u,v,ne,num; 11 }q[sj*2]; 12 void add(int x,int y){ 13     b[e].u=x; 14     b[e].v=y; 15     b[e].ne=h[x]; 16     h[x]=e++; 17 } 18 int find(int x){ 19     if(fa[x]==-1){ 20         return x; 21     } 22     fa[x]=find(fa[x]); 23     return fa[x]; 24 } 25 void hb(int x,int y){ 26     x=find(x); 27     y=find(y); 28     if(x!=y){ 29         fa[x]=y; 30     } 31     return ; 32 } 33 void lca(int x){ 34     zx[x]=x; 35     re[x]=1; 36     for(int i=h[x];i!=-1;i=b[i].ne){ 37         if(!re[b[i].v]){ 38             lca(b[i].v); 39             hb(x,b[i].v); 40             zx[find(b[i].v)]=x; 41         } 42     } 43     for(int i=l[x];i!=-1;i=q[i].ne){ 44         if(re[q[i].v]){ 45             ans[q[i].num]=zx[find(q[i].v)]; 46         } 47     } 48     return ; 49 } 50 void adq(int x,int y,int z){ 51     q[f].u=x; 52     q[f].v=y; 53     q[f].num=z; 54     q[f].ne=l[x]; 55     l[x]=f++; 56     return ; 57 } 58 void dfs(int x){ 59     for(int i=h[x];i!=-1;i=b[i].ne){ 60         if(!re[b[i].v]){ 61             re[b[i].v]=1; 62             dep[b[i].v]=dep[x]+1; 63             dfs(b[i].v); 64             po[x]+=po[b[i].v]; 65        } 66     } 67     return ; 68 } 69 int main(){ 70     cin>>n>>m; 71     memset(h,-1,sizeof(h)); 72     memset(fa,-1,sizeof(fa)); 73     memset(l,-1,sizeof(l)); 74     for(int i=1;i
       
        >a1>>a2; 76         add(a1,a2); 77         add(a2,a1); 78     } 79     for(int i=1;i<=m;i++){ 80         cin>>a1>>a2; 81         adq(a1,a2,i); 82         adq(a2,a1,i); 83         po[a1]++; 84         po[a2]++; 85     } 86     lca(1); 87     for(int i=1;i<=m;i++){ 88         po[ans[i]]-=2; 89     } 90     memset(re,0,sizeof(re)); 91     re[1]=1; 92     dep[1]=1; 93     dfs(1); 94     for(int i=0;i
        
         dep[b[i].u]){103             if(po[b[i].v]==0){104                 jg+=m;105             }else if(po[b[i].v]==1){106                 jg++;107             }108         }109     }110     cout<
         
          <