文章

倍增lca(路径有权值)

#include<bits/stdc++.h>
using namespace std;
const long long int maxn=2e5+10;
long long int n,cnt=0,res=0;
long long int head[maxn],b[maxn],lg[maxn],fa[maxn][30];
long long int vis[maxn],fu[maxn][30],deep[maxn];
struct edge{
	long long int to,nex,val;
}e[maxn];
void add(long long int u,long long int v,long long int t){
	cnt++;
	e[cnt].to=v;
	e[cnt].nex=head[u];
	e[cnt].val=t;
	head[u]=cnt;
	return ;
}
void dfs(long long int now,long long int par,long long int val){
	long long int i,v;
	if(vis[now]==1) return ;
	vis[now]=1; 
	fa[now][0]=par;
	fu[now][0]=val;
	deep[now]=deep[par]+1;
	for(i=1;i<=lg[now];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
		fu[now][i]=fu[now][i-1]+fu[fa[now][i-1]][i-1];
	}
	for(i=head[now];i!=0;i=e[i].nex){
		v=e[i].to;
		if(v!=par){
			dfs(v,now,e[i].val);
		}
	}
	return ;
}
long long int lca(long long int u,long long int v){
	long long int ans=0;
	long long int t,k;
	if(deep[u]<deep[v]){
		t=u;
		u=v;
		v=t;
	}	
	while(deep[u]!=deep[v]){
		ans+=fu[u][lg[deep[u]-deep[v]]];
		u=fa[u][lg[deep[u]-deep[v]]];
	}
	if(u==v){
		return ans;
	}
	for(k=lg[deep[u]];k>=0;k--){
		if(fa[u][k]!=fa[v][k]){
			ans+=( fu[u][k] +fu[v][k] );
			u=fa[u][k];
			v=fa[v][k];
		}
	}
	return ans+fu[u][0]+fu[v][0];
}
int main()
{
	long long int t,i,u,v,k; 
	cin>>n>>k;
	for(i=1;i<n;i++){
		cin>>u>>v>>t;
		add(u,v,t);
		add(v,u,t);
	}
//	cout<<"cnt "<<cnt<<endl;
	for(i=1;i<=k;i++){
		cin>>b[i];
	}
	for(i=2;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
//	cout<<"YES"<<endl;
	dfs(1,0,0);
//	cout<<"lca ";
	for(i=1;i<k;i++){
		res+=lca(b[i],b[i+1]);
//		cout<<lca(b[i],b[i+1])<<' ';
	}
//	cout<<endl;
//	cout<<res<<endl;
//	cout<<"YES"<<endl;
	for(i=1;i<=k;i++){
		if(i==1){
			cout<<res-lca(b[i],b[i+1])<<" ";
		}else if(i==k){
			cout<<res-lca(b[k],b[k-1]);
		}else {
			cout<<res-lca(b[i],b[i-1])-lca(b[i],b[i+1])+lca(b[i-1],b[i+1])<<" ";
		}
	}
	cout<<endl;
	return 0;
}

License:  CC BY 4.0