3717.【NOI2014模拟7.2】火车(train)

(File IO): input:train.in output:train.out Time Limits: 3000 ms Memory Limits: 512MB

Description A国有n个城市，城市之间有一些双向道路相连，并且城市两两之间有唯一路径。现在有火车在城市a，需要经过m个城市。火车按照以下规则行驶：每次行驶到还没有经过的城市中在m个城市中最靠前的。现在小A想知道火车经过这m个城市后所经过的道路数量。

Input 第一行三个整数n、m、a，表示城市数量、需要经过的城市数量，火车开始时所在位置。 接下来n-1行，每行两个整数x和y，表示x和y之间有一条双向道路。 接下来一行m个整数，表示需要经过的城市。

Output 一行一个整数，表示火车经过的道路数量。

Sample Input

5 4 2 1 2 2 3 3 4 4 5 4 3 1 5

Sample Output

9

Data Constraint

---

题目大意

给出一棵树，与当前所在的位置，让你在某个状态时走到数列中最靠前的没有到过的点（也就是说，如果在走到某个点的过程中，走到了某个在数列中这个位置之后的点，那么之后就不用再走到那个点去了），求所走的边数个数。

考场上某位神犇大佬看错题了。。。就因为那有毒的样例，没注意到不用再走走过的点

---

解题思路

---

这题很显然啊

Solution1 LCA 一看到求树上距离，马上就想到了LCA了吧。 对于要走到的那个点，如果之前到过的，就跳过，没到过的话，求当前位置与目标位置的lca，计算距离，暴力标记路径中的点，并查集维护点不被重复标记。 复杂度：LCA: O(nlogn+mlogn) ，并查集 O(nlogn) ，总体 O((2n+m)logn)

记得开long long

codes:

#include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N=505010; const int bit=22; int n,m,a,to[N*2],top,nex[N*2],fir[N],fa[bit][N],nxt[N],bz[N],deep[N],T,sta[N],head,tail,que[N]; long long ans=0; int read(){ char ch;int ans;for(;(ch=getchar())>'9' || ch<'0';);ans=ch-'0'; for(;(ch=getchar())>='0' && ch<='9';)ans=(ans<<1)+(ans<<3)+(ch-'0');return ans; } void link(int x,int y){ to[++top]=y;nex[top]=fir[x];fir[x]=top; } void init(){ int x,y,i; for(head=0,deep[que[tail=1]=1]=1;head!=tail;) for(i=fir[x=que[++head]];i;i=nex[i]) if((y=to[i])!=fa[0][x])fa[0][que[++tail]=y]=x,deep[y]=deep[x]+1; } int lca(int x,int y){ if(deep[x]<deep[y])swap(x,y); for(int diff=deep[x]-deep[y],i=0;diff;diff>>=1,i++)if(diff & 1)x=fa[i][x]; if(x==y)return x; for(int i=21;i+1;i--)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];return fa[0][x]; } int get(int x){ int ans; for(;nxt[x]!=x;x=nxt[x])sta[++T]=x;sta[++T]=x; for(int i=1;i<T;i++)nxt[sta[i]]=sta[T];ans=sta[T];T=0; return ans; } void con(int x,int y){ int b=get(y);nxt[x]=b; } int main(){ freopen("train.in","r",stdin); freopen("train.out","w",stdout); n=read();m=read();a=read(); for(int i=1;i<=n;i++)nxt[i]=i; for(int i=1;i<n;i++){ int x=read(),y=read(); link(x,y),link(y,x); }init(); for(int j=1;j<22;j++)for(int i=1;i<=n;i++)fa[j][i]=fa[j-1][fa[j-1][i]]; bz[a]=1;nxt[a]=fa[0][a]; for(int i=1,las=a;i<=m;i++){ int x=read(),l,tx,ty; if(!bz[x]){ l=lca(las,x);tx=las,ty=x; ans+=(long long)(deep[las]+deep[x]-deep[l]*2); for(tx=get(tx);deep[tx]>=deep[l];tx=nxt[tx])bz[tx]=1,con(tx,fa[0][tx]); for(;deep[ty]>=deep[l];ty=nxt[ty])bz[ty]=1,con(ty,fa[0][ty]); las=x; } } printf("%lld",ans); fclose(stdin);fclose(stdout); return 0; }

Solution2 LCT 这是个更显然的想法 添边连边 直接求两点距离，区间标记+lazytag

#include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=500100; int pre[N],fa[N],son[N][2],n,m,a,siz[N],T,sta[N]; bool rev[N],bz[N],laz[N]; ll ans=0; int read(){ char ch;int ans;for(;(ch=getchar())>'9' || ch<'0';);ans=ch-'0'; for(;(ch=getchar())>='0' && ch<='9';)ans=(ans<<1)+(ans<<3)+(ch-'0');return ans; } bool isroot(int x){return son[fa[x]][0]!=x && son[fa[x]][1]!=x;} int dir(int x){return son[fa[x]][1]==x;} void update(int x){ if(!x)return; siz[x]=siz[son[x][0]]+siz[son[x][1]]+1; } void rotate(int x){ int y=fa[x],w=dir(x); fa[x]=fa[y];if(fa[x])son[fa[x]][dir(y)]=x;fa[y]=x; son[y][w]=son[x][1^w];if(son[y][w])fa[son[y][w]]=y;son[x][1^w]=y; pre[x]=pre[y];update(y); } void node(int x){ if(!x)return;bz[x]=1;laz[x]=1; } void reverse(int x){ if(!x)return;rev[x]^=1; swap(son[x][0],son[x][1]); } void down(int x){ if(!x)return; if(laz[x])laz[x]=0,node(son[x][0]),node(son[x][1]); if(rev[x])rev[x]=0,reverse(son[x][0]),reverse(son[x][1]); } void up(int x){ for(;!isroot(x);x=fa[x])sta[++T]=x;sta[++T]=x; while(T)down(sta[T--]); } void splay(int x){ up(x); for(;!isroot(x);rotate(x)){ int y=fa[x]; if(isroot(y))continue; (dir(x)^dir(y))?rotate(x):rotate(y); }update(x); } void access(int x){ for(int y=0;x;y=x,x=pre[x]){ splay(x);fa[son[x][1]]=0;pre[son[x][1]]=x; fa[y]=x;pre[y]=0;son[x][1]=y;update(x); } } void makeroot(int x){access(x);splay(x);reverse(x);} void link(int x,int y){makeroot(x);splay(y);pre[x]=y;} void takenode(int x,int y){makeroot(x);access(y);splay(x);node(x);} bool noded(int x){splay(x);return bz[x];} int len(int x,int y){makeroot(x);access(y);splay(y);return siz[y]-1;} int main(){ freopen("train.in","r",stdin); freopen("train.out","w",stdout); n=read();m=read();a=read(); for(int i=1;i<=n;i++)siz[i]=1; for(int i=1;i<n;i++){ int x=read(),y=read();link(x,y); } takenode(a,a); for(int i=1,las=a;i<=m;i++){ int x=read(); if(!noded(x)){ ans+=(ll)len(las,x); takenode(las,x);las=x; } } printf("%lld",ans); fclose(stdin);fclose(stdout); return 0; }