蒟蒻求助!!!
查看原帖
蒟蒻求助!!!
437643
huangboyu楼主2022/9/12 10:41
#include<bits/stdc++.h>
#define ll long long
#define INF 9999999999999999 
using namespace std;
const int N=1e5+5;
int n,s,q,E;
struct EDGE{
	int to,nxt,data,id;
}e[2*N];
int ux[N],vy[N],shop[N];
int head[N],cnt,c[N],dfn[N];
ll f[N],dis[N];
void add(int u,int v,int w,int i){
	e[++cnt].to =v;
	e[cnt].nxt =head[u];
	e[cnt].data =w;
	e[cnt].id =i;
	head[u]=cnt;
}
int fa[N],dep[N],top[N],son[N],size[N];
void dfs(int now){
	size[now]=1;
	if(shop[now])f[now]=0;
	for(int i=head[now];i;i=e[i].nxt ){
		int to=e[i].to;
		if(to==fa[now])continue;
		dep[to]=dep[now]+1;
		dis[to]=dis[now]+e[i].data;
		fa[to]=now;dfs(to);
			
		shop[now]+=shop[to];
		size[now]+=size[to];
		f[now]=min(f[now],f[to]+e[i].data);
		if(size[to]>size[son[now]])son[now]=to;
	}
}
int cnt2;
void dfs1(int now,int tp){
	top[now]=tp;dfn[now]=++cnt2;
	if(son[now])dfs1(son[now],tp);
	for(int i=head[now];i;i=e[i].nxt ){
		int to=e[i].to;
		if(to==fa[now]||to==son[now])
			continue;
		dfs1(to,to);
	}
}
long long val[N<<2];
void change(int now,int l,int r,ll v,int id){
	if(id<l||id>r)return ;
	if(l==r){
		val[now]=v;
		return;
	}
	int mid=l+r>>1;
	change(now<<1,l,mid,v,id);
	change(now<<1|1,mid+1,r,v,id);
	val[now]=min(val[now<<1],val[now<<1|1]);
	return;
}
ll ask(int now,int l,int r,int L,int R){
	if(L<=l&&r<=R)return val[now];
	if(l>R||r<L)return INF;
	int mid=l+r>>1;
	ll val1=ask(now<<1,l,mid,L,R);
	ll val2=ask(now<<1|1,mid+1,r,L,R);
	return min(val1,val2);
}
long long ask_val(int x,int y){
	ll res=INF;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])
			swap(x,y);
		res=min(res,ask(1,1,n,dfn[x],dfn[y]));
		y=fa[top[y]];
	}
	if(dfn[x]>dfn[y])swap(x,y);
	res=min(res,ask(1,1,n,dfn[x],dfn[y]));
	return res;
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])
			swap(x,y);
		y=fa[top[y]];
	}
	if(dep[x]<dep[y])return x;
	else return y;
}
bool flag=1;
int main(){
	scanf("%d%d%d%d",&n,&s,&q,&E);
	for(int i=1;i<n;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		ux[i]=a;vy[i]=b;
		f[i]=INF;
		add(a,b,w,i);add(b,a,w,i);
	}f[n]=INF;
	for(int i=1;i<=s;i++)
		scanf("%d",&c[i]),shop[c[i]]=1;
	dep[E]=1;dfs(E);dfs1(E,E);
	for(int i=1;i<=n;i++)
		change(1,1,n,f[i]-dis[i],dfn[i]);
	while(q--){
		int Id,r;
		scanf("%d%d",&Id,&r);
		int u=ux[Id],v=vy[Id];
		if(dep[u]<dep[v])swap(u,v);
		if(lca(u,r)==u){
			if(!shop[u])printf("oo\n");
			else printf("%lld\n",ask_val(v,r)+dis[r]);
		}
		else printf("escaped\n");
	}
	return 0;
}
2022/9/12 10:41
加载中...