HDU 2586

http://acm.hdu.edu.cn/showproblem.php?pid=2586
题意：求最近祖先节点的权值和
思路：LCA Tarjan算法
 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 40005
 4 
 5 int m,n,x[maxn],y[maxn],z[maxn],head[maxn*2],pos,dist[maxn],f[maxn];   
 6 bool vis[maxn];
 7 struct Edge{
 8     int to,val,next;
 9 }edge[maxn*2];
10 
11 
12 void add(int u,int v,int val)
13 {
14     edge[pos].to = v;
15     edge[pos].val = val;
16     edge[pos].next = head[u];
17     head[u] = pos++;
18 }
19 
20 int Find(int x)
21 {
22     if(f[x]!=x)
23         return f[x] =Find(f[x]);
24     return f[x];
25 }
26 
27 void Tarjan(int u)
28 {
29     vis[u] = true;
30     f[u] = u;
31     for(int i = 1;i<=n;i++)
32     {
33         if(x[i]==u&&vis[y[i]]) z[i] = Find(y[i]);
34         if(y[i]==u&&vis[x[i]]) z[i] = Find(x[i]);
35     }
36     for(int i =head[u];i!=-1;i=edge[i].next)
37     {
38         int v = edge[i].to;
39         if(!vis[v])
40         {
41             dist[v] =dist[u]+edge[i].val;
42             Tarjan(v);
43             f[v] = u;
44         }
45     }
46 }
47 
48 int main()
49 {
50     int t,a,b,c;
51     scanf("%d",&t);
52     while(t--)
53     {
54         scanf("%d%d",&m,&n);
55         memset(head,-1,sizeof(head));
56         memset(vis,false,sizeof(vis));
57 
58         pos = 1;
59         for(int i = 1;i<m;i++)
60         {
61             scanf("%d%d%d",&a,&b,&c);
62             add(a,b,c);
63             add(b,a,c);
64             z[i] = 0;
65         }
66         z[m] = 0;
67         for(int i = 1; i<=n;i++)
68         {
69             scanf("%d%d",&x[i],&y[i]);  //分别存每一次的查询点。
70         }
71         dist[1] = 0;
72         Tarjan(1);
73         for(int i = 1;i<=n;i++)
74             printf("%d
",dist[x[i]]+dist[y[i]]-2*dist[z[i]]);
75     }
76     return 0;
77 }