为什么会MLE呢

P1600 [NOIP2016 提高组] 天天爱跑步

01bit @ 2021-07-12 21:53:48

#include<cstdio>
#include<vector>
using namespace std;
struct Edge{
    int v;
    int next;
}edge[600005];
struct Graph{
    int cnt=0,head[300005]={};
    void addedge(int u,int v){
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
}G;
struct Tree{
    int fa[300005]={},dep[300005]={},g[300005][25]={};
    Tree(){
        init(1);
    }
    void init(int x){
        for(int i=G.head[x];i;i=edge[i].next){
            int v=edge[i].v;
            if(v==fa[x])continue;
            init(v);
            dep[v]=dep[x]+1;
            g[v][0]=fa[v]=x;
            for(int j=1;j<=20;j++)g[v][j]=g[g[v][j-1]][j-1];
        }
    }
    int lca(int x,int y){
        int tmp=0;
        if(dep[x]<dep[y])tmp=x,x=y,y=tmp,tmp=0;
        int jump=dep[x]-dep[y],b=0;
        while(jump){
            if(jump&1)x=g[x][b];
            jump>>=1;
            b++;
        }
        if(x==y)return x;
        for(int i=20;i>=0;i--)
            if(g[x][i]!=g[y][i]){
                x=g[x][i];
                y=g[y][i];
            }
        return g[x][0];
    }
}tree;
int n,m;
static int s[300005],t[300005],w[300005];
static int buc[300005]={},bg[300005]={},ans[300005]={},dis[300005]={},anc[300005]={};
static vector<int> l[300005],e[300005];
void dfs1(int x){
    int f=buc[tree.dep[x]+w[x]];
    for(int i=G.head[x];i;i=edge[i].next){
        if(edge[i].v==tree.fa[x])continue;
        dfs1(edge[i].v);
    }
    buc[tree.dep[x]]+=bg[x];
    ans[x]+=buc[tree.dep[x]+w[x]]-f;
    for(int i=0;i<l[x].size();i++)buc[tree.dep[t[l[x][i]]-dis[l[x][i]]]]--;
}
void dfs2(int x){
    int f=buc[tree.dep[x]-w[x]];
    for(int i=G.head[x];i;i=edge[i].next){
        if(edge[i].v==tree.fa[x])continue;
        dfs2(edge[i].v);
    }
    buc[tree.dep[x]]+=bg[x];
    for(int i=0;i<e[x].size();i++)buc[tree.dep[t[e[x][i]]-dis[e[x][i]]]]--;
    ans[x]+=buc[tree.dep[x-w[x]]]-f;
    for(int i=0;i<l[x].size();i++)buc[tree.dep[t[l[x][i]]-dis[l[x][i]]]]--;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G.addedge(u,v);
        G.addedge(v,u);
    }
    for(int i=1;i<=n;i++)scanf("%d",w+i);
    for(int i=1;i<=m;i++){
        scanf("%d%d",s+i,t+i);
        int lca=tree.lca(s[i],t[i]);
        anc[i]=lca;
        dis[i]=tree.dep[s[i]]+tree.dep[t[i]]-2*tree.dep[lca];
        l[lca].push_back(i);
        e[t[i]].push_back(i);
        ++bg[s[i]];
    }
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=m;i++)if(tree.dep[anc[i]]+w[anc[i]]==tree.dep[s[i]])ans[anc[i]]--;
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

|