求助虚树板子,数组开到1e7 RE70分 求大佬看看为什么QWQ
  • 板块学术版
  • 楼主Deepth
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/26 18:43
  • 上次更新2023/11/3 07:31:18
查看原帖
求助虚树板子,数组开到1e7 RE70分 求大佬看看为什么QWQ
788123
Deepth楼主2023/7/26 18:43

(同求RE调试方法,不开放数据) https://www.luogu.com.cn/record/117506093

#include <bits/stdc++.h>
#define int long long
#define db double
#define D if(0)
using namespace std;
const int N = 1e7+10,P=1e9+7;
#define out(a) {for(int __=0; __<20;__++)print((a)[__]);cout<<"\n";}
template<typename T>void print(T x){cout<<x<<" ";}
int rd(){
    static int fu,num;static char ch;fu=1,num=0;
    while(!isdigit(ch)){if(ch=='-')fu=-1;ch=getchar();}
    while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}
    return fu*num;
}
int n,m,k,T,cnt=1,ans,h[N];
struct EDGE{
    int u,v,n,w;
}e[N*4];
void add(int u,int v,int w){
    e[++cnt]={u,v,h[u],w};
    h[u]=cnt;
    e[++cnt]={v,u,h[v],w};
    h[v]=cnt;
}
int fa[N],dfn[N],son[N],top[N],siz[N],dep[N],w[N];
void dfs0(int u,int f){
    fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].v;
        if(v==f)continue;
        w[v]=min(w[u],e[i].w);
        dfs0(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs1(int u,int tp){
    top[u]=tp;dfn[u]=++dfn[0];
    if(son[u])dfs1(son[u],tp);
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].v;
        if(v==fa[u]||v==son[u])continue;
        dfs1(v,v);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
        else y=fa[top[y]];
    }
    return dep[x]<dep[y]?x:y;
}
vector<int> vec;
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void build(){
    vec.push_back(1);
    sort(vec.begin(),vec.end(),cmp);
    for(auto i=vec.begin(),R=vec.end()-1;i<R;i++)vec.push_back(lca(*i,*(i+1)));
    sort(vec.begin(),vec.end(),cmp);
    auto end=unique(vec.begin(),vec.end());
    // for(auto i=vec.begin();i<vec.end();i++)cout<<*i<<" ";
    // cout<<endl;
    // for(auto i=vec.begin();i<end;i++)cout<<*i<<" ";
    // cout<<"--------\n";
    for(auto i=vec.begin();i<end-1;i++){
        int l=lca(*i,*(i+1));
        // cout<<l<<" "<<*(i+1)<<endl;
        add(l,*(i+1),0);
    }
}
int f[N];
int dp(int u,int ff){
    int ans=0;
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].v;
        if(v==ff)continue;
        ans+=dp(v,u);
    }
    if(f[u])return w[u];
    return u==1?ans:min(ans,w[u]);
}
int work(){
    build();
    return dp(1,0);
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    memset(w,0x3f,sizeof(w));
    cin>>n;
    for(int i=1;i<n;i++){
        int u=rd(),v=rd(),w=rd();
        add(u,v,w);
    }
    dfs0(1,0);
    // out(fa)out(son)
    // out(dfn)
    dfs1(1,1);
    // out(top)
    // out(dfn)
    D out(w)
    cnt=1;
    memset(h,0,sizeof(h));
    cin>>m;
    for(int i=1;i<=m;i++){
        int ki=rd();
        vec.clear();
        for(int j=1;j<=ki;j++){
            int u=rd();f[u]=1;
            vec.push_back(u);
        }
        cout<<work()<<endl;
        for(auto i:vec)h[i]=f[i]=0;
        cnt=1;
    }
    fclose(stdin);
    fclose(stdout);
}
2023/7/26 18:43
加载中...