描述

車展結(jié)束后，游樂園決定舉辦一次盛大的山道拉力賽，平平和韻韻自然也要來參加大賽。

賽場上共有n個連通的計時點，n-1條賽道（構(gòu)成了一棵樹）。每個計時點的高度都不相同（父結(jié)點的高度必然大于子結(jié)點），相鄰計時點間由賽道相連。由于馬力不夠，所以韻韻的遙控車只能從高處駛向低處。而且韻韻的車跑完每條賽道都需花費一定的時間。

舉辦方共擬舉辦m個賽段的比賽，每次從第u個計時點到第v個計時點，當(dāng)然其中有不少比賽韻韻的遙控車是不能參加的（因為要上坡）。平平想知道他能參加多少個賽段的比賽，并且想知道他完成這些賽段的總用時。

賽道皆為單向。

格式

輸入格式

第一行兩個整數(shù)n，m。

接下來n-1行每行3個整數(shù)a、b、t。

表示韻韻的遙控車可以花t秒從第a個計時點到第b個計時點。

接下來m行每行2個整數(shù)u、v，意義如描述所示。

輸出格式

第一行輸出一個正整數(shù)，表示能參加的賽段數(shù)。

第二行輸出一個正整數(shù)，表示總用時。

樣例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％的數(shù)據(jù) n≤1000 m≤1000；
對于100％的數(shù)據(jù) 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/937337156Zhang/p/6052410.html

總結(jié)

以上是生活随笔為你收集整理的vijos p1460——拉力赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。