Vijos——T1406 拉力赛

1460

描述

车展结束后，游乐园决定举办一次盛大的山道拉力赛，平平和韵韵自然也要来参加大赛。

赛场上共有n个连通的计时点，n-1条赛道（构成了一棵树）。每个计时点的高度都不相同（父结点的高度必然大于子结点），相邻计时点间由赛道相连。由于马力不够，所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。

举办方共拟举办m个赛段的比赛，每次从第u个计时点到第v个计时点，当然其中有不少比赛韵韵的遥控车是不能参加的（因为要上坡）。平平想知道他能参加多少个赛段的比赛，并且想知道他完成这些赛段的总用时。

赛道皆为单向。

格式

输入格式

第一行两个整数n，m。

接下来n-1行每行3个整数a、b、t。

表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。

接下来m行每行2个整数u、v，意义如描述所示。

输出格式

第一行输出一个正整数，表示能参加的赛段数。

第二行输出一个正整数，表示总用时。

样例1

样例输入1

样例输出1

1
2

限制

各个测试点1s

提示

第一个计时点的高度是最高的；
u≠v；
对于50％的数据 n≤1000 m≤1000；
对于100％的数据 n≤10000 m≤100000；
答案小于2^64。

来源

f1zsy birdor

按标签就开始码，结果~LCA 60~

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 #define LL long long
 8 
 9 const int N(100000+15);
10 LL n,m,u,v,w;
11 
12 LL head[N],sumedge;
13 struct Edge
14 {
15     LL u,v,w,next;
16     Edge(LL u=0,LL v=0,LL next=0,LL w=0):
17         u(u),v(v),next(next),w(w){}
18 }edge[N];
19 void ins(LL u,LL v,LL w)
20 {
21     edge[++sumedge]=Edge(u,v,head[u],w);
22     head[u]=sumedge;
23 }
24 
25 LL dis[N],size[N],deep[N],dad[N],top[N];
26 void DFS(LL x)
27 {
28     size[x]=1; deep[x]=deep[dad[x]]+1;
29     for(int i=head[x];i;i=edge[i].next)
30     {
31         LL v=edge[i].v;
32         if(dad[x]!=v)
33         {
34             dad[v]=x;
35             dis[v]=dis[x]+edge[i].w,
36             DFS(v),size[x]+=size[v];
37         }            
38     }
39 }
40 
41 void DFS_(LL x)
42 {
43     LL t=0; if(!top[x]) top[x]=x;
44     for(int i=head[x];i;i=edge[i].next)
45     {
46         LL v=edge[i].v;
47         if(dad[x]!=v&&size[t]<size[v]) t=v;
48     }
49     if(t) top[t]=top[x],DFS_(t);
50     for(int i=head[x];i;i=edge[i].next)
51     {
52         LL v=edge[i].v;
53         if(dad[x]!=v&&t!=v) DFS_(v);
54     }
55 }
56 
57 LL LCA(LL x,LL y)
58 {
59     for(;top[x]!=top[y];x=top[dad[x]])
60         if(deep[top[x]]<deep[top[y]]) swap(x,y);
61     return deep[x]<deep[y]?x:y;
62 }
63 
64 LL ansnum,anstim;
65 
66 int main()
67 {
68     cin>>n>>m;
69     for(int i=1;i<n;i++)
70         cin>>u>>v>>w,ins(u,v,w),ins(v,u,w);
71     DFS(1);DFS_(1);
72     for(;m;m--)
73     {
74         cin>>u>>v;
75         if(u==LCA(u,v))
76             ansnum++,anstim+=dis[v]-dis[u];
77     }
78     cout<<ansnum<<endl<<anstim;
79     return 0;
80 }

AWWAWAAAWA

然后看题解，用sta记录点的先序遍历，ove记录后序遍历，

如果sta[u]<sta[v]&&ove[u]>ove[v]就说明u是v的祖先~

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int M(100000+15);
 7 int n,m,u,v,ansnum;
 8 long long w,anstim;
 9 
10 int head[M],sumedge;
11 struct Edge
12 {
13     int u,v,next,dis;
14     long long w;
15     Edge(int u=0,int v=0,int next=0,int dis=0):
16         u(u),v(v),next(next),dis(dis){}
17 }edge[M];
18 void ins(int u,int v,int w)
19 {
20     edge[++sumedge]=Edge(u,v,head[u],w);
21     head[u]=sumedge;
22 }
23 
24 int dis[M],sta[M],ove[M],tim;
25 void DFS(int now,int val)
26 {
27     sta[now]=++tim; dis[now]=val;
28     for(int i=head[now];i;i=edge[i].next)
29         DFS(edge[i].v,val+edge[i].dis);
30     ove[now]=++tim;
31 }
32 
33 int main()
34 {
35     scanf("%d%d",&n,&m);
36     for(int i=1;i<n;i++)
37         scanf("%d%d%I64d",&u,&v,&w),ins(u,v,w);
38     DFS(1,0);
39     for(;m;m--)
40     {
41         scanf("%d%d",&u,&v);
42         if(sta[u]<sta[v]&&ove[u]>ove[v])
43             ansnum++,anstim+=dis[v]-dis[u];
44     }
45     cout<<ansnum<<endl<<anstim;
46     return 0;
47 }

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。