样例过,求调
查看原帖
样例过,求调
1162380
liverxiwo楼主2024/4/7 13:38

wa一堆,0分求调

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int fa[500005],f0[500005],dep[500005],siz[500005];
int headson[500005],v[500005],d[500005],pre[500005];
int dfn1[500005],dfn2[500005];
int cnt,n,Q,k;
bool vis[500005];
vector<pair<int,int> > g[500005];
int mi[500005];
int ls(int x){
	return x<<1;
}
int rs(int x){
	return x<<1|1;
}
void updata(int x){
	mi[x]=min(mi[ls(x)],mi[rs(x)]);
	return ;
}
void build(int x,int l,int r){
	if(l==r){
		mi[x]=dfn2[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	updata(x);
	return ;
}
int query(int x,int l,int r,int ll,int rr){
	if(ll<=l&&rr>=r){
		return mi[x];
	}
	int mid=(l+r)>>1;
	int ans=1e18;
	if(mid>=ll){
		ans=min(ans,query(ls(x),l,mid,ll,rr));
	}
	if(mid<rr){
		ans=min(ans,query(rs(x),mid+1,r,ll,rr));
	}
	return ans;
}
int dfs1(int x,int fa){
	siz[x]=1;
	for(auto it:g[x]){
		int to=it.second;
		if(!(to^fa)){
			v[x]=it.first;
			continue;
		}
		siz[x]+=dfs1(to,x);
		if(siz[to]>siz[headson[x]]){
			headson[x]=to;
		}
	}
	return siz[x];
}
void dfs2(int x,int father,int fa0){
	dep[x]=dep[father]+1;
	fa[x]=father;
	f0[x]=fa0;
	dfn2[++cnt]=d[x];
	dfn1[x]=cnt;
	if(f0[father]==fa0){
		pre[x]=pre[father]+v[x];
	}
	else{
		pre[x]=v[x];
	}
	if(!headson[x]){
		return ;
	}
	dfs2(headson[x],x,fa0);
	for(auto it:g[x]){
		int to=it.second;
		if(to==father||to==headson[x]){
			continue;
		}
		dfs2(to,x,to);
	}
	return ;
}
int ask(int x,int y){
	int sum=0,dis=1e12;
	while(f0[x]!=f0[y]){
		if(dep[f0[x]]>dep[f0[y]]){
			sum+=pre[x];
			dis=min(dis,query(1,1,n,dfn1[f0[x]],dfn1[x]));
			x=fa[f0[x]];
		}
		else{
			sum+=pre[y];
			dis=min(dis,query(1,1,n,dfn1[f0[x]],dfn1[x]));
			y=fa[f0[y]];
		}
	}
	dis=min(dis,query(1,1,n,min(dfn1[x],dfn1[y]),max(dfn1[x],dfn1[y])));
	sum+=abs(pre[x]-pre[y])+(dis<<1);
	return sum;
}
signed main(){
	scanf("%lld%lld%lld",&n,&Q,&k);
	for(int i=1;i<=n-1;i++){
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		g[x].push_back({z,y});
		g[y].push_back({z,x});
	}
	priority_queue<pair<int,int> > q;
	for(int i=1;i<=k;i++){
		int x;
		scanf("%lld",&x);
		d[x]=0;
		q.push({0,x});
	}
	while(!q.empty()){
		int val=q.top().first,x=q.top().second;
		q.pop();
		if(vis[x]){
			continue;
		}
		vis[x]=true;
		for(auto it:g[x]){
			if(!vis[it.second]){
				if(d[it.second]>d[x]+it.first);
				d[it.second]=d[x]+it.first;
				q.push({-d[it.second],it.second});
			}
		}
	}
	dfs1(1,0);
	dfs2(1,0,1);
	build(1,1,n);
	for(int i=1;i<=Q;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		int ans=ask(x,y);
		printf("%lld\n",ans);
    }
	return 0;
}
2024/4/7 13:38
加载中...