MLE20分,请问哪儿数组开大了/kel
查看原帖
MLE20分,请问哪儿数组开大了/kel
160839
Prean楼主2020/7/15 23:22

/kel/kel/kel

#include<algorithm>
#include<cstdio>
const int M=2.5e5+5,INF=0x7fffffff;
struct Edge{
    int to,val;
    Edge*nx;
}e[M<<1],*h[M],*cnt=e;
int n,q,m,tot,dis,d[M],id[M],log[M],f[M][20],len[M][20];
int top,a[M],stk[M];bool vis[M];
inline int min(const int a,const int b){
    return a>b?b:a;
}
inline bool cmp(const int u,const int v){
    return id[u]<id[v];
}
void init(int u){
    id[u]=++tot;
    d[u]=d[f[u][0]]+1;
    for(int i=1;(1<<i)<=d[u];++i){
        f[u][i]=f[f[u][i-1]][i-1];
        len[u][i]=min(len[u][i-1],len[f[u][i-1]][i-1]);
    }
    for(Edge*E=h[u];E;E=E->nx){
        int v=E->to;
        if(d[v])continue;
        f[v][0]=u;len[v][0]=E->val;
        init(v);
    }
    h[u]=NULL;
}
inline int LCA(int u,int v){
    dis=INF;
    if(d[u]<d[v])u^=v^=u^=v;
    while(d[u]!=d[v]){
        int l=log[d[u]-d[v]];
        dis=min(dis,len[u][l]);
        u=f[u][l];
    }
    if(u==v)return u;
    for(int i=log[d[u]];i>=0;--i){
        if(f[u][i]!=f[v][i]){
            dis=min(dis,min(len[u][i],len[v][i]));
            u=f[u][i];v=f[v][i];
        }
    }
    return f[u][0];
}
long long DFS(int u,int val=INF){
    long long dp=0;
    for(Edge*E=h[u];E;E=E->nx){
        int v=E->to;
        if(u==1&&vis[v])dp+=E->val;
        else if((dp+=DFS(v,E->val))>=val)return h[u]=NULL,val;
    }
    if(!dp&&vis[u])dp=val;
    return h[u]=NULL,dp;
}
inline void Add(int u,int v,int val=0){
    if(!val)LCA(u,v),val=dis;
    *cnt=(Edge){v,val,h[u]};h[u]=cnt++;
}
inline void Insert(int u){
    if(!top)return void(stk[++top]=u);
    int v=LCA(stk[top],u);
    while(top>1&&d[v]<d[stk[top-1]])Add(stk[--top],stk[top]);
    if(d[stk[top]]>d[v])Add(v,stk[top--]);
    if(!top||stk[top]!=v)stk[++top]=v;
    if(stk[top]!=u)stk[++top]=u;
}
signed main(){
    int i,x,y,z;
    scanf("%d",&n);log[0]=-1;
    for(i=1;i<=n;++i)log[i]=log[i>>1]+1;
    for(i=1;i<n;++i){ 
        scanf("%d%d%d",&x,&y,&z);
        Add(x,y,z);Add(y,x,z);
    }
    init(1);
    scanf("%d",&q);
    while(q--){
        cnt=e;top=0;
        scanf("%d",&m);
        for(i=1;i<=m;++i)scanf("%d",a+i),vis[a[i]]=true;
        std::sort(a+1,a+m+1,cmp);
        m=std::unique(a+1,a+m+1)-a-1;
        if(a[1]!=1)stk[++top]=1;
        for(i=1;i<=m;++i)Insert(a[i]);
        while(top>1)Add(stk[--top],stk[top]);
        printf("%lld\n",DFS(1));
        for(i=1;i<=m;++i)vis[a[i]]=false;
    }
}
2020/7/15 23:22
加载中...