虚树板题WA on #10求助
查看原帖
虚树板题WA on #10求助
177000
vicky2048_2楼主2023/5/15 20:03

所有变量都开Long Long了,数组初始化有需要的话设置的也都是LL_MAX,真的找不到那里写挂了……QAQ

#include<bits/stdc++.h>
#define int long long
#define N 250005
using namespace std;
int n,m,p[N],fp[N],fa[N],mindis[N],lca(int,int),son[N],dep[N],cnt,fir[N],pos,sz[N],t[N],node[N],num,fi[N],cn,dp[N],note[N],get_ans(int);
void dfs1(int,int),dfs2(int,int),add(int,int,int),build(),ad(int,int);
bool  xyl(int a,int b){ return p[a]<p[b];}
struct E{
    int nxt,to,dis;
}e[N<<1],ed[N<<1];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        mindis[i+1]=LONG_LONG_MAX;
        int a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
        add(a,b,c);
    } mindis[1]=LONG_LONG_MAX;
    dfs1(1,1),dfs2(1,1);
    scanf("%lld",&m);
    while(m--){
        scanf("%lld",&num);
        for(int i=1;i<=num;i++) scanf("%lld",&node[i]),note[node[i]]=m;
        sort(node+1,node+1+num,xyl);
        build();
        printf("%lld\n",get_ans(1));
    }
    return 0;
}
void build(){
    int a[N],len=0; a[++len]=1;
    for(int i=1;i<num;i++)
        a[++len]=node[i],a[++len]=lca(node[i],node[i+1]);
    a[++len]=node[num];
    sort(a+1,a+1+len,xyl);
    len=unique(a+1,a+1+len)-a-1;
    cn=0;
    for(int i=1;i<len;i++){
        int lc=lca(a[i],a[i+1]);
        ad(lc,a[i+1]);
    }
}
int get_ans(int no){
    int ans=0;
    for(int i=fi[no];i;i=ed[i].nxt){
        int v=ed[i].to;
        ans+=get_ans(v);
    }
    fi[no]=0;
    if(note[no]==m) return no==1?ans:mindis[no];
    else return min(mindis[no],ans);
}
int lca(int a,int b){
    while(t[a]!=t[b]){
        if(dep[t[a]]>dep[t[b]]) a=fa[t[a]];
        else b=fa[t[b]];
    }
    return dep[a]>dep[b]?b:a;
}
void dfs1(int no,int faa){
    fa[no]=faa,++sz[no];
    for(int i=fir[no];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=faa){
            dep[v]=dep[no]+1,mindis[v]=min(mindis[no],e[i].dis);
            dfs1(v,no);
            sz[no]+=sz[v];
            if(sz[v]>sz[son[no]]) son[no]=v;
        }
    }
}
void dfs2(int no,int top){
    p[no]=++pos,fp[pos]=no,t[no]=top;
    if(!son[no]) return ;
    dfs2(son[no],top);
    for(int i=fir[no];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=fa[no]&&v!=son[no]) dfs2(v,v);
    }
}
void add(int a,int b,int c){
    e[++cnt].to=b,e[cnt].nxt=fir[a],e[cnt].dis=c,fir[a]=cnt;
    e[++cnt].to=a,e[cnt].nxt=fir[b],e[cnt].dis=c,fir[b]=cnt;
}
void ad(int a,int b){
    ed[++cn].to=b,ed[cn].nxt=fi[a],fi[a]=cn;
}
2023/5/15 20:03
加载中...