[悬关] MnZn 求助虚树,快及掩了。
查看原帖
[悬关] MnZn 求助虚树,快及掩了。
371825
SalN楼主2024/4/1 09:17

可以过 #1,#9,#10,别的都 wa 了 /dk

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
#define mp make_pair
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)

using namespace std;

const int N=800010, K=25, inf=1ll<<60;

int n, m, t, p, a[N], dep[N], L[N], R[N], tc, f[N];
int F[N][K], tot, stk[N], top, mi[N];
vector<pii> to[N];

void dfs(int x,int fa) {
	L[x]=++tc;
	dep[x]=dep[fa]+1, F[x][0]=fa;
	up(i,1,t) F[x][i]=F[F[x][i-1]][i-1];
	for(pii p:to[x]) {
		int y=p.first, val=p.second;
		if(y!=fa) mi[y]=min(mi[x],val), dfs(y,x);
	}
	R[x]=++tc;
}

int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	dn(i,t,0) if(dep[F[x][i]]>=dep[y]) x=F[x][i];
	if(x==y) return x;
	dn(i,t,0) if(F[x][i]!=F[y][i]) x=F[x][i], y=F[y][i];
	return F[x][0];
}

bool cmp_dfn(int x,int y) { int l=(x>0)?L[x]:R[-x], r=(y>0)?L[y]:R[-y]; return l<r; }

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n, t=log2(n);
	up(i,2,n) {
		int u, v, w;
		cin >> u >> v >> w;
		to[u].pb(mp(v,w));
		to[v].pb(mp(u,w));
	}
	cin >> m, mi[1]=inf, dfs(1,0);
	while(m--) {
		cin >> p, tot=p;
		up(i,1,p) cin >> a[i], f[a[i]]=mi[a[i]];
		sort(a+1,a+1+p,cmp_dfn);
		up(i,2,p) a[++tot]=lca(a[i-1],a[i]);
		sort(a+1,a+1+tot), tot=unique(a+1,a+1+tot)-a-1;
		if(a[1]!=1) a[++tot]=1;
		up(i,1,tot) a[tot+i]=-a[i];
		tot<<=1, top=0, sort(a+1,a+1+tot,cmp_dfn);
		up(i,1,tot) {
			if(a[i]>0) stk[++top]=a[i];
			else {
				int x=stk[top];
				--top;
				int fa=stk[top];
				if(fa) f[fa]+=min(mi[x],f[x]);
			}
		}
		cout << f[1] << '\n';
		up(i,1,tot) if(i>0) f[i]=0;
	}
	return 0;
}
2024/4/1 09:17
加载中...