LG2495 「SDOI2011」消耗战虚树

问题描述

题解

虚树

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=250007;

const int INF=0x3f3f3f3f3f3f3f3fLL;

int n,T,k;

int tot,Head[maxn],to[maxn<<2],Next[maxn<<2],w[maxn<<2];

int size[maxn],son[maxn],mn[maxn];

int fa[maxn],dep[maxn],top[maxn];

int dfn[maxn],ind;

void add(int x,int y,int z){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;

}

void dfs1(int x,int f,int dp){

	fa[x]=f,dep[x]=dp,size[x]=1;

	int mx=-1;

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;

		mn[y]=min(mn[x],w[i]);

		dfs1(y,x,dp+1);size[x]+=size[y];

		if(size[y]>mx) mx=size[y],son[x]=y;

	}

}

void dfs2(int x,int tp){

	top[x]=tp,dfn[x]=++ind;

	if(!son[x]) return;

	dfs2(son[x],tp);

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==fa[x]||y==son[x]) continue;

		dfs2(y,y);

	}

}

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]];

	}

	if(dep[x]>dep[y]) swap(x,y);

	return x;

}

int s[maxn],ttop;

int a[maxn];

vector<int>v[maxn];

void insert(int x){

	if(ttop==1){s[++ttop]=x;return;}

	int lc=lca(x,s[ttop]);

	if(lc==s[ttop]) return;

	while(ttop>1&&dfn[s[ttop-1]]>=dfn[lc]){

		v[s[ttop-1]].push_back(s[ttop]);ttop--;

	}

	if(lc!=s[ttop]){v[lc].push_back(s[ttop]);s[ttop]=lc;}

	s[++ttop]=x;

}

bool comp(int a,int b){

	return dfn[a]<dfn[b];

}

int dp(int x){

	if(!v[x].size()) return mn[x];

	int res=0;

	for(int i=0;i<v[x].size();i++){

		res+=dp(v[x][i]);

	}

	v[x].clear();

	return min(res,mn[x]);

}

signed main(){

	read(n);mn[1]=INF;

	for(int i=1,x,y,z;i<n;i++){

		read(x);read(y);read(z);

		add(x,y,z);add(y,x,z);

	}

	dfs1(1,0,1);dfs2(1,1);

	read(T);

	while(T--){

		read(k);

		for(int i=1;i<=k;i++) read(a[i]);

		sort(a+1,a+k+1,comp);

		s[ttop=1]=1;

		for(int i=1;i<=k;i++) insert(a[i]);

		while(ttop>0) v[s[ttop-1]].push_back(s[ttop]),ttop--;

		printf("%lld\n",dp(1));

	}

	return 0;

}

巴特西

LG2495 「SDOI2011」消耗战虚树

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG2495 「SDOI2011」消耗战 虚树

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

LG2495 「SDOI2011」消耗战虚树