萌新刚学虚树WA20pts求助
查看原帖
萌新刚学虚树WA20pts求助
752774
KAxdd楼主2023/12/25 09:29

rt,

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=250005;
int n,m,q;
int dep[MAXN],dfn[MAXN],a[MAXN],son[MAXN],siz[MAXN],top[MAXN],fa[MAXN],lg[MAXN],cnt=0,dp[MAXN];
int stk[MAXN],tail=0,Minn[MAXN];
int head[MAXN<<1],to[MAXN<<1],nxt[MAXN<<1],w[MAXN<<1],tot=0;
void add(int x,int y,int z) {
    to[++tot]=y;
    nxt[tot]=head[x];
    w[tot]=z;
    head[x]=tot;
}
vector<int> p[MAXN];
map<int,int> ma,vis;
bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}
void dfs1(int x,int faa) {
    dep[x]=dep[faa]+1;
    fa[x]=faa;
    dfn[x]=++cnt;
    siz[x]=1;
    for(int i=head[x];i;i=nxt[i]) {
        if(to[i]==faa) continue;
        Minn[to[i]]=min(Minn[x],w[i]);
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        if(siz[son[x]]<siz[to[i]]) son[x]=to[i];
    }
}
void dfs2(int x,int topf) {
	top[x]=topf;
	if(!son[x]) return ;
	dfs2(son[x],topf);
	for(int i=head[x];i;i=nxt[i]) {
		if(to[i]==fa[x] || to[i]==son[x]) continue;
		dfs2(to[i],to[i]);
	}
}
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;
}
void Add(int x,int y) {
    p[x].push_back(y);
    ma[x]++; ma[y]++;
}
void dfs3(int x,int fa) {
    if(!p[x].size()) {
        dp[x]=Minn[x];
        return ;
    }
    dp[x]=0;
    for(auto i:p[x]) {
        if(i==fa) continue;
        dfs3(i,x);
        if(!vis[i]) dp[x]+=dp[i];         
        else dp[x]+=min(Minn[i],dp[i]);           
    }
    p[x].clear();
}
void insert(int x){
    if(tail==1) {
        if(x!=1) stk[++tail]=x;
        return ;
    }
    int l=lca(x,stk[tail]);
    if(l==stk[tail]) return ;
    for(;tail>1 && dfn[stk[tail-1]]>=dfn[l];tail--) {
        Add(stk[tail-1],stk[tail]);
    }
    if(stk[tail]!=l) {
        Add(l,stk[tail]);
        stk[tail]=l;
    }
    stk[++tail]=x;
}
signed main() {
    scanf("%lld",&n);
    for(int i=1;i<n;i++) {
        int x,y,z;
        scanf("%lld %lld %lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    Minn[1]=1e18;
    dfs1(1,0);
    dfs2(1,1);
    scanf("%lld",&q);
    while(q--) {
        scanf("%lld",&m);
        vis.clear();
        ma.clear(); 
        for(int i=1;i<=m;i++) scanf("%lld",&a[i]),vis[a[i]]++;
        sort(a+1,a+m+1,cmp);
        tail=0;
        stk[++tail]=1;
        for(int i=1;i<=m;i++) insert(a[i]);
        while(tail>1) Add(stk[tail-1],stk[tail]),tail--; 
        dfs3(1,0);
        printf("%lld\n",dp[1]);
        for(auto i:ma) dp[i.first]=0;
        
    }
    return 0;
}
2023/12/25 09:29
加载中...