求助虚树,WA#50pts
查看原帖
求助虚树,WA#50pts
339568
TonviaSzt楼主2023/3/25 17:02
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=250005;
int n,m,k,tim,p[N],dfn[N],dep[N],a[N],fa[N][21],bz[N];
LL minv[N],dp[N];
vector<int> R[N];
struct qh{
    int v;
    LL w;
    int nt;
}E[N<<1];
struct H{
    int x,pos;
}h[N];
inline int Rd(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}
inline void add(int u,int v,int w){E[++p[0]]=(qh){v,w,p[u]};p[u]=p[0];return ;}
void dfs(int u,int f){
    dfn[u]=++tim;dep[u]=dep[f]+1;
    fa[u][0]=f;
    for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=p[u];i;i=E[i].nt){
        int v=E[i].v;
        if(v==f) continue;
        minv[v]=min(minv[u],E[i].w);
        dfs(v,u);
    }return ;
}
int Lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
bool c1(H x,H y){return dfn[x.x]<dfn[y.x];}
void build(){
    sort(h+1,h+k+1,c1);
    // for(int i=1;i<=k;i++) printf("%d ",h[i].x);
    a[0]=0;
    a[++a[0]]=1;
    for(int i=1;i<k;i++){
        if(h[i].x==1) continue;
        a[++a[0]]=h[i].x;
        int l=Lca(h[i].x,h[i+1].x);
        if(l==a[a[0]]) continue;
        else{
            while (dep[l]<dep[a[a[0]-1]]){
                R[a[a[0]]].push_back(a[a[0]-1]);
                R[a[a[0]-1]].push_back(a[a[0]]);
                a[0]--;
            }
            if(dep[l]>dep[a[a[0]-1]]){
                R[h[i].x].push_back(l);
                R[l].push_back(h[i].x);
                a[a[0]]=l;
            }
            else{
                R[a[a[0]]].push_back(a[a[0]-1]);
                R[a[a[0]-1]].push_back(a[a[0]]);
                a[0]--;
            }
            // printf("%d %d %d\n",h[i].x,h[i+1].x,l);
        }
    }
    a[++a[0]]=h[k].x;
    // printf("%d\n",R[1].size());
    // for(int i=1;i<=a[0];i++) printf("%d ",a[i]);
    while (a[0]>1) R[a[a[0]]].push_back(a[a[0]-1]),R[a[a[0]-1]].push_back(a[a[0]]),a[0]--;
    return ;
}
LL DP(int x,int f){
    LL sum=0,ret;
    for(int i=0;i<R[x].size();i++){
        int v=R[x][i];
        if(v==f) continue;
        sum+=DP(v,x);
    }
    // printf("x:%d sum:%lld minv:%lld\n",x,sum,minv[x]);
    if(bz[x]) ret=minv[x];
    else ret=min(minv[x],sum);
    bz[x]=0;
    R[x].clear();
    return ret;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    #endif
    n=Rd();
    for(int i=1;i<=n;i++) minv[i]=1e18;
    for(int i=1;i<n;i++){
        int u=Rd(),v=Rd(),w=Rd();
        add(u,v,w);add(v,u,w);
    }
    dfs(1,0);
    // for(int i=1;i<=n;i++) printf("%d ",minv[i]);puts("");
    // for(int i=1;i<=n;i++){
    //     printf("%d:",i);
    //     for(int j=0;j<=20;j++) printf("%d ",fa[i][j]);
    //     printf("\n");
    // }
    m=Rd();
    while (m--){
        tim=0;p[0]=0;
        k=Rd();
        for(int i=1;i<=k;i++) h[i]={Rd(),i},bz[h[i].x]=1;
        build();
        // for(int i=1;i<=n;i++){
        //     printf("%d:",i);
        //     for(int j=0;j<R[i].size();j++) printf("%d ",R[i][j]);
        //     printf("\n");
        // }
        printf("%lld\n",DP(1,0));
    }
    return 0;
}
/*
start coding:10:43
stop:11:00
continue:11:12
stop:12:00
continue:14:55 //finish building virtual tree
pass the example:15:33
stop:16:11
continue:16:24
stop:17:00
finish debuging:
*/
2023/3/25 17:02
加载中...