描述
車展結束后，游樂園決定舉辦一次盛大的山道拉力賽，平平和韻韻自然也要來參加大賽。
賽場上共有n個連通的計時點，n-1條賽道（構成了一棵樹）。每個計時點的高度都不相同（父結點的高度必然大于子結點），相鄰計時點間由賽道相連。由于馬力不夠，所以韻韻的遙控車只能從高處駛向低處。而且韻韻的車跑完每條賽道都需花費一定的時間。
舉辦方共擬舉辦m個賽段的比賽，每次從第u個計時點到第v個計時點，當然其中有不少比賽韻韻的遙控車是不能參加的（因為要上坡）。平平想知道他能參加多少個賽段的比賽，并且想知道他完成這些賽段的總用時。
賽道皆為單向。
格式
輸入格式
第一行兩個整數n，m。
接下來n-1行每行3個整數a、b、t。
表示韻韻的遙控車可以花t秒從第a個計時點到第b個計時點。
接下來m行每行2個整數u、v，意義如描述所示。
輸出格式
第一行輸出一個正整數，表示能參加的賽段數。
第二行輸出一個正整數，表示總用時。
樣例1
樣例輸入1
6 2
1 2 1
2 4 1
2 5 1
5 6 1
1 3 1
2 6
4 5 樣例輸出1
1
2 限制
各個測試點1s
提示
第一個計時點的高度是最高的；
u≠v；
對于50％的數據 n≤1000 m≤1000；
對于100％的數據 n≤10000 m≤100000；
答案小于2^64。
?
LCA，只用記錄下deep就可以了，LCA判斷x和y的公共祖先是否為x或y若是的話加上時間即可。
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<cstring>
5 using namespace std;
6 const int maxn=10005;
7 int fa[maxn][20],deep[maxn];
8 int head[maxn],nextn[maxn],tov[maxn],w[maxn];
9 int pd[maxn];
10 int n,m,tot;int d[maxn];
11 long long t,ans;
12 void go(int x,int y,int z)
13 {
14 tot++;
15 nextn[tot]=head[x];
16 head[x]=tot;
17 tov[tot]=y;
18 w[tot]=z;
19 }
20
21 void dfs(int x)
22 {
23 int v=head[x];
24 while(v)
25 {
26 if(pd[tov[v]]==false)
27 {
28 fa[tov[v]][0]=x;
29 deep[tov[v]]=deep[x]+1;
30 d[tov[v]]=d[x]+w[v];
31 pd[tov[v]]=true;
32 int ii=0,pos=x;
33 while(fa[pos][ii])
34 {
35 fa[tov[v]][ii+1]=fa[pos][ii];
36 pos=fa[pos][ii];
37 ii++;
38 }
39 dfs(tov[v]);
40 }
41 v=nextn[v];
42 }
43 }
44 void lca(int x,int y)
45 {
46 if(deep[x]>deep[y])return ;
47 int m=deep[y]-deep[x];
48 int ii=0;
49 int k=y;
50 while(m)
51 {
52 if(m&1)y=fa[y][ii];
53 m=(m>>1);
54 ii++;
55 }
56 if(x!=y)return ;
57 ans++;
58 t+=d[k]-d[x];
59 }
60 int main()
61 {
62 scanf("%d%d",&n,&m);
63 for(int i=1;i<=n-1;i++)
64 {
65 int x,y,z;
66 scanf("%d%d%d",&x,&y,&z);
67 go(x,y,z);
68 }
69 deep[1]=1;pd[1]=true;
70 dfs(1);
71 for(int i=1;i<=m;i++)
72 {
73 int x,y;
74 scanf("%d%d",&x,&y);
75 lca(x,y);
76 }
77 printf("%I64d\n",ans);
78 printf("%I64d\n",t);
79 return 0;
80 } ?
