题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2953
起点为1，每次求两个点的距离，然后加在一起。
|
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 |
#include<bits/stdc++.h> #define maxn 30030 #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n; int deep[maxn],fa[maxn],tp[maxn],sz[maxn],hson[maxn]; vector<int>go[maxn]; void dfs1(int now){ sz[now]=1; for(int i=0; i<go[now].size(); i++){ int to=go[now][i]; if(to==fa[now])continue; fa[to]=now; deep[to]=deep[now]+1; dfs1(to); sz[now]+=sz[to]; if(sz[to]>sz[hson[now]])hson[now]=to; } } void dfs2(int now,int t){ tp[now]=t; if(hson[now])dfs2(hson[now],t); for(int i=0; i<go[now].size(); i++){ int to=go[now][i]; if(to==fa[now] || to==hson[now])continue; dfs2(to,to); } } inline int lca(int x,int y){ while(tp[x]!=tp[y]){ if(deep[tp[x]]<deep[tp[y]])swap(x,y); x=fa[tp[x]]; } if(deep[x]<deep[y])swap(x,y); return y; } inline void init(){ n=rd(); for(int i=1; i<n; i++){ int x=rd(),y=rd(); go[x].pb(y); go[y].pb(x); } } inline int dis(int x,int y){ return deep[x]+deep[y]-2*deep[lca(x,y)]; } inline void work(){ dfs1(1); dfs2(1,1); int m=rd(),ans=0,now=1; while(m--){ int to=rd(); ans+=dis(now,to); now=to; } printf("%d\n",ans); } int main(){ init(); work(); return 0; } |
