STEP5::Problem 0134 : 景點問題

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0134
很有趣(?!)的題目。
只要找出LAC就可以了。第一次寫LAC所以寫得很難看。

題目有說兩點只有一條路徑–>這是一棵樹。找出兩點的路徑長就是a點到root+b點到root-2*LAC到root。(好像也可以直接從兩點回朔找LCA—Online LCA Sparse Table,不過我那時候不知道ㄏ…..)
至於怎麼做就是把樹壓扁成陣列,再用線段樹搜區間內深度最小的那點(就LAC啦)。不過因為不用更新,所以可以用Sparsr Table寫,O(n lg n+q)。(下面是用BIT寫的)
(再)至於怎麼壓扁要用時間標記,把DFS的時候進出的順序記錄下來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#define N 30002
using namespace std;
vector<int> T[N];
int A[2*N],F[N],H[2*N],BT[8*N];
int Buildtree(int le,int re,int id)
{
if(le==re){BT[id]=A[le];return A[le];}
int tmp1,tmp2;
tmp1=Buildtree(le,(le+re)/2,id*2);
tmp2=Buildtree((le+re)/2+1,re,id*2+1);
BT[id]= (H[tmp1]<H[tmp2])? tmp1:tmp2;
//printf("Q %d,%d:%d\n",le,re,A[le]);
return BT[id];
}
int find(int a,int b,int le,int re,int id)
{
if(re==le)return BT[id];
if(re<a||le>b)return -1;
if(a<=le&&re<=b)return BT[id];
int tmp=(re+le)/2,tmp1,tmp2;
if(le==re)
return BT[id];
tmp1=find(a,b,le,tmp,id*2);
tmp2=find(a,b,tmp+1,re,id*2+1);
//printf("YYY:%d:%d %d:%d\n",le,tmp1,re,tmp2);
if(tmp1!=-1 && tmp2!=-1)
return (H[tmp1] < H[tmp2])? tmp1:tmp2;
else
return (tmp1!=-1)? tmp1:tmp2;
}
int DFS(int now,int no,int dr,int tm)
{
//printf("%d ",tm);
A[tm]=now;
F[now]=tm;
H[tm]=dr;
for(int i=0;i*2<T[now].size();i++)
if(T[now][i*2] != no){
tm += 1;
tm = DFS(T[now][i*2],now,dr+T[now][i*2+1],tm);
tm = tm+1;
//printf("%d ",tm);
A[tm]=now;
H[tm]=dr;
}
return tm;
}
int main(int argc,char *argv[])
{
int n;
scanf("%d",&n);
int a,b,c;
for(int i=1;i<n;i++){
scanf("%d %d %d",&a,&b,&c);
a++;b++;
T[a].push_back(b);
T[a].push_back(c);
T[b].push_back(a);
T[b].push_back(c);
}
int tm=1;
tm = DFS(1,-1,0,tm);
Buildtree(1,tm,1);
int q,now=1,qw,sum=0;
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&qw);
qw++;
a=(F[now] <= F[qw])? F[now]:F[qw];
b=(F[now] > F[qw])? F[now]:F[qw];
c=find(a,b,1,tm-1,1);
sum+=H[a]+H[b]-H[c]-H[c];
//printf("OO:%d(%d %d %d %d) \n",H[a]+H[b]-H[c]-H[c],a,b,H[c],sum);
now=qw;
}
printf("%d\n",sum);
//system("pause");
return 0;
}