虚树模板/P2495 [SDOI2011] 消耗战

FJOI / 2023-05-19 / 原文

\(\color{purple}\text{P2495 [SDOI2011] 消耗战}\)

所谓虚树，就是对树上 \(dp\) 的优化，建立一棵新树，上面包含原树的部分节点，且父子关系不变。套路是他会有很多个询问，每个询问涉及一些关键点，但是总关键点数 \(\le 10^5\) 之类。
建树复杂度 \(O(n \log n)\)

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2.5e5+110,M=1e6+110;
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
} 
struct Tree_edge{
	int head[N],last[M],to[M],w[M],tot;
	void add(int u,int v,int t){to[++tot]=v,w[tot]=t,last[tot]=head[u],head[u]=tot;return;}
}E1,E2;
int n,dep[N],dfn[N],CntDfn,f[N][21],mw[N][21];//2^18>2.5e5 
void dfs(int u,int h){
	dfn[u]=++CntDfn;dep[u]=h;
	for(int i=E1.head[u];i;i=E1.last[i]){
		int v=E1.to[i];if(v==f[u][0])continue;
		f[v][0]=u,mw[v][0]=E1.w[i],dfs(v,h+1);
	}
	return;
}

int LCApos,LCAva;
void LCA(int x,int y){
	LCAva=2e9;
	if(dep[x]<dep[y])swap(x,y);
	int de=dep[x]-dep[y];
	for(int i=18;i>=0;i--)
		if(de&(1<<i))LCAva=min(LCAva,mw[x][i]),x=f[x][i];
	for(int i=18;i>=0;i--)
		if(f[x][i]!=f[y][i]){
			LCAva=min(LCAva,mw[x][i]),x=f[x][i];
			LCAva=min(LCAva,mw[y][i]),y=f[y][i];
		}
	if(x!=y){
		LCAva=min(LCAva,mw[x][0]),x=f[x][0];
		LCAva=min(LCAva,mw[y][0]),y=f[y][0];
	}
	LCApos=x;return;
}

int m,keypos[N],st[M],top;
int rcd[N],lenrcd;int dp[N],vis[N];
bool cmp(int A,int B){return dfn[A]<dfn[B];}
void DP(int u){
	if(vis[u]){dp[u]=2e17;return;} 
	dp[u]=0;
	for(int i=E2.head[u];i;i=E2.last[i]){
		int v=E2.to[i];DP(v);
		dp[u]+=min(dp[v],E2.w[i]);
	}
	return;
}
void solve(){
	top=0;for(int i=1;i<=lenrcd;i++)E2.head[rcd[i]]=0;E2.tot=0;lenrcd=0;
	
	int k=read();for(int i=1;i<=k;i++)keypos[i]=read(),vis[keypos[i]]=1;
	sort(keypos+1,keypos+k+1,cmp);
	for(int i=1;i<k;i++){
		st[++top]=keypos[i];
		LCA(keypos[i],keypos[i+1]);st[++top]=LCApos;
	}st[++top]=keypos[k];
	sort(st+1,st+top+1,cmp);
	top=unique(st+1,st+top+1)-st-1
	for(int i=1;i<top;i++){
		LCA(st[i],st[i+1]);int tmp=LCApos;
		LCA(tmp,st[i+1]);
		E2.add(tmp,st[i+1],LCAva);rcd[++lenrcd]=tmp;
	}
	if(st[1]!=1){
		LCA(1,st[1]);
		E2.add(1,st[1],LCAva),rcd[++lenrcd]=1;
	}
	DP(1);printf("%lld\n",dp[1]);
	
	for(int i=1;i<=k;i++)vis[keypos[i]]=0;
	return;
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),t=read();
		E1.add(u,v,t),E1.add(v,u,t);
	}
	dfs(1,1);
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++)
			f[j][i]=f[f[j][i-1]][i-1],
			mw[j][i]=min(mw[j][i-1],mw[f[j][i-1]][i-1]);
	m=read();for(int i=1;i<=m;i++)solve();
	return 0;
}