p8855MLE9个点求调树剖Lca
  • 板块题目总版
  • 楼主liaoxingrui
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/18 14:34
  • 上次更新2024/3/18 19:23:30
查看原帖
p8855MLE9个点求调树剖Lca
744895
liaoxingrui楼主2024/3/18 14:34
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int n,a,b,m,x,xx=1,ans,tot;
int fa[N],dep[N],siz[N],son[N],top[N],head[N];
struct node{
	int x,y;
}next[N<<1];
inline void add(int x,int y){
	tot++;
	next[tot].x=y;
	next[tot].y=head[x];
	head[x]=tot;
}
inline void dfs1(int node){
	siz[node]=1;
	for(int i=head[node];i;i=next[i].y){
		int w=next[i].x;
		if(w!=fa[node]){
			fa[w]=node;
			dep[w]=dep[node]+1;
			dfs1(w);
			siz[node]+=siz[w];
			if(siz[w]>siz[son[node]])
				son[node]=w;
		}
	}
}
inline void dfs2(int node,int x){
	top[node]=x;
	if(!son[node])
		return;
	dfs2(son[node],x);
	for(int i=head[x];i;i=next[i].y){
		int w=next[i].x;
		if(w!=fa[node]&&w!=son[node])
			dfs2(w,w);
	}
}
inline int Lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs1(1);
	dfs2(1,1);
	cin>>m;
	while(m--){
		cin>>x;
		ans+=dep[x]+dep[xx]-2*dep[Lca(x,xx)];
		xx=x;
	}
	cout<<ans;
	return 0;
}
2024/3/18 14:34
加载中...