[bzoj3910] 火车

　　一开始看错题了...

　　求经过的道路数量就求个lca，把路径上的点置为已经过的话，可以写一个并查集，把某个点往上连续已经过的一段点并起来。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define d double

 #define ll long long

 using namespace std;

 const int maxn=;

 struct zs{int too,pre;}e[maxn<<];int tot,last[maxn];

 int dep[maxn],fa[maxn],dfn[maxn],bel[maxn],sz[maxn],tim,f[maxn];

 bool gg[maxn];

 int i,j,k,n,m;

 ll ans;

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 void dfs(int x){

     sz[x]=,dep[x]=dep[fa[x]]+;

     for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x])

         fa[e[i].too]=x,dfs(e[i].too),sz[x]+=sz[e[i].too];

 }

 void dfs2(int x,int chain){

     int i,mx=;

     bel[x]=chain,dfn[x]=++tim;

     for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&sz[e[i].too]>sz[mx])mx=e[i].too;

     if(!mx)return;

     dfs2(mx,chain);

     for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&e[i].too!=mx)dfs2(e[i].too,e[i].too);

 }

 inline int getlca(int a,int b){

     while(bel[a]!=bel[b]){

         if(dep[bel[a]]<dep[bel[b]])swap(a,b);

         a=fa[bel[a]];

     }

     return dep[a]<dep[b]?a:b;

 }

 inline int getf(int x){return f[x]!=x?f[x]=getf(f[x]):x;}

 inline void run(int x,int lca){

     lca=getf(lca);//printf("lca:   %d\n",lca);

     while(getf(x)!=lca)

         x=f[x],f[x]=lca,x=fa[x];

     gg[lca]=;

 }

 inline void insert(int a,int b){

     e[++tot].too=b,e[tot].pre=last[a],last[a]=tot,

     e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;

 }

 int main(){int st,lca;

     n=read(),m=read(),st=read();

     for(i=;i<n;i++)insert(read(),read());

     for(i=;i<=n;i++)f[i]=i;

     dfs(),dfs2(,);

     for(i=;i<=m;i++){

         j=read();

         if(gg[getf(j)])continue;

         lca=getlca(st,j),run(st,lca),run(j,lca),

         ans+=dep[j]+dep[st]-(dep[lca]<<),st=j;

 //      for(printf("done:  "),j=1;j<=n;j++)if(gg[getf(j)])printf("   %d",j);puts("");

     }

     printf("%lld\n",ans);

 }