萌新求调虚树(玄关)
查看原帖
萌新求调虚树(玄关)
614509
c21162wqb楼主2024/7/26 08:26
#include<bits/stdc++.h>
#define int long long 
#define N 250010
#define M 500010
using namespace std;
vector<int>a[N],z[N];
int f[N][20],dep[N],dfn[N],cnt,mn[N][20];
void dfs(int x,int fa) {
    dfn[x]=++cnt,dep[x]=dep[fa]+1,f[x][0]=fa;
    for(int i=1;i<=19;i++) {
        f[x][i]=f[f[x][i-1]][i-1];
        mn[x][i]=min(mn[f[x][i-1]][i-1],mn[x][i-1]);
    }
    for(int i=0;i<a[x].size();i++) {
        int v=a[x][i],w=z[x][i];
        if(v==fa) continue ;
        mn[v][0]=w;
        dfs(v,x);
    }
}
int sum;
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    sum=1e15;
    for(int i=19;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) {
            sum=min(sum,mn[x][i]);
            x=f[x][i];
        }
    if(x==y) return x;
    for(int i=19;i>=0;i--) 
       if(f[x][i]!=f[y][i]) {
            sum=min(sum,min(mn[x][i],mn[y][i]));
            x=f[x][i],y=f[y][i];
        }
    sum=min(sum,min(mn[x][0],mn[y][0]));
    return f[x][0];
}
vector<int>aa[N],zz[N];
int k[M],m,top,st[N];
void build() {
    top=1,st[1]=1,zz[1].clear(),aa[1].clear();
    for(int i=1;i<=m;i++) {
        if(k[i]==1) continue ;
        int fa=lca(st[top],k[i]);
        if(fa!=st[top]) {
            while(dfn[fa]<dfn[st[top-1]]) {
                int u=st[top-1],v=st[top];
                lca(u,v);
                aa[u].push_back(v),zz[u].push_back(sum);
                top--;
            }
            if(fa!=st[top-1]) {
                int u=fa,v=st[top];
                lca(u,v);
                zz[u].clear(),aa[v].clear();
                aa[u].push_back(v),zz[u].push_back(sum);
                st[top]=u;
            }
            else {
                int u=st[top-1],v=st[top];
                lca(u,v);
                aa[u].push_back(v),zz[u].push_back(sum);
                top--;
            }
        }
        zz[k[i]].clear(),aa[k[i]].clear();
        st[++top]=k[i];
    }
    for(int i=1;i<top;i++) {
        int u=st[i],v=st[i+1];
        lca(u,v);
        aa[u].push_back(v),zz[u].push_back(sum);
    }
}
int dp[N],pd[N];
void dfs2(int x) {
    dp[x]=0;
    for(int i=0;i<aa[x].size();i++) {
        int v=aa[x][i],w=zz[x][i];
        dfs2(v);
        if(pd[v]>0) dp[x]+=w;
        else dp[x]+=min(dp[v],w);
    }
}
bool cmp(int a,int b) {
    return dfn[a]<dfn[b];
}
int n,q;
signed main() {
    cin>>n;
    for(int i=1;i<n;i++) {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        a[u].push_back(v),a[v].push_back(u);
        z[u].push_back(w),z[v].push_back(w);
    }
    memset(mn,32,sizeof(mn));
    dfs(1,1);
    cin>>q;
    while(q--) {
        scanf("%lld",&m);
        for(int i=1;i<=m;i++) {
            scanf("%lld",&k[i]);
            pd[k[i]]=1;
        }
        sort(k+1,k+m+1,cmp);
        build();
        dfs2(1);
        printf("%lld\n",dp[1]);
        for(int i=1;i<=m;i++) pd[k[i]]=0;
    }
    return 0;
}
2024/7/26 08:26
加载中...