题目连接：http://poj.org/problem?id=3417
tarjan+树DP
来自：http://www.cnblogs.com/scau20110726/archive/2013/05/31/3110666.html
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const int N=100005; 7 const int Q=100005; 8 9 int te,tq; 10 int heade[N],headq[N],dp[N],f[N],vis[N]; 11 struct edge 12 { 13 int u,v,nex; 14 }e[N*2]; 15 16 struct query 17 { 18 int u,v,lca,nex; 19 }q[Q*2]; 20 21 void adde(int u,int v) 22 { 23 e[te].v=v; 24 e[te].u=u; 25 e[te].nex=heade[u]; 26 heade[u]=te++; 27 } 28 void addq(int u,int v) 29 { 30 q[tq].u=u; 31 q[tq].v=v; 32 q[tq].lca=-1; 33 q[tq].nex=headq[u]; 34 headq[u]=tq++; 35 } 36 int gf(int x) 37 { 38 return x==f[x]?x:f[x]=gf(f[x]); 39 } 40 41 void tarjan(int u) 42 { 43 vis[u]=1; 44 for(int i=headq[u];i!=-1;i=q[i].nex) 45 if(vis[q[i].v]) 46 { 47 int v=q[i].v; 48 int lca=gf(v); 49 q[i].lca=q[i^1].lca=lca; 50 } 51 for(int i=heade[u];i!=-1;i=e[i].nex) 52 if(!vis[e[i].v]) 53 { 54 int v=e[i].v; 55 tarjan(v); 56 f[v]=u; 57 } 58 } 59 60 void DP(int u) 61 { 62 vis[u]=1; 63 for(int i=heade[u];i!=-1;i=e[i].nex) 64 if(!vis[e[i].v]) 65 { 66 int v=e[i].v; 67 DP(v); 68 dp[u]+=dp[v]; 69 } 70 } 71 int main() 72 { 73 int n,t; 74 75 while(scanf("%d%d",&n,&t)!=EOF) 76 { 77 te=tq=0; 78 memset(heade,-1,sizeof(heade)); 79 memset(headq,-1,sizeof(headq)); 80 memset(dp,0,sizeof(dp)); 81 memset(vis,0,sizeof(vis)); 82 for(int i=1;i<=n;i++) f[i]=i; 83 for(int i=1;i<n;i++) 84 { 85 int u,v; 86 scanf("%d%d",&u,&v); 87 adde(u,v); 88 adde(v,u); 89 } 90 for(int i=0;i<t;i++) 91 { 92 int u,v; 93 scanf("%d%d",&u,&v); 94 addq(u,v); 95 addq(v,u); 96 dp[u]++; 97 dp[v]++; 98 } 99 tarjan(1); 100 for(int i=0;i<t;i++) 101 { 102 int s=i*2; 103 int lca=q[s].lca; 104 dp[lca]-=2; 105 } 106 memset(vis,0,sizeof(vis)); 107 DP(1); 108 int res=0; 109 for(int i=2;i<=n;i++) 110 if(dp[i]==1) res++; 111 else if(dp[i]==0) res+=t; 112 printf("%d\n",res); 113 114 } 115 }
