关于时间复杂度

帮帮萌新/kel

这个代码时间复杂度是啥啊

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int n,m;
int Head[N],Next[N<<1],V[N<<1],cnt;
void add(int u,int v){
    V[cnt]=v;
    Next[cnt]=Head[u];
    Head[u]=cnt++;
}
int w[N];
int depth[N],dfn[N],ou[N<<1],top;
void dfs(int x,int fa){
    ou[++top]=x;
    dfn[x]=top;
    depth[x]=depth[fa]+1;
    for(int i=Head[x];i!=-1;i=Next[i]){
        if(V[i]!=fa){
            dfs(V[i],x);
            ou[++top]=x;
        }
    }
}
int Log[N<<1],st[N<<1][20];
int calc(int x,int y){return depth[ou[x]]<depth[ou[y]]?x:y;}
void ST(){
    Log[0]=-1;
    for(int i=1;i<=top;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=top;i++)st[i][0]=i;
    for(int j=1;(1<<j)<=top;j++){
        for(int i=1;i+(1<<j)-1<=top;i++){
            st[i][j]=calc(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}
int LCA(int x,int y){
    int fx=dfn[x],fy=dfn[y];
    if(fy<fx)swap(fx,fy);
    int k=Log[fy-fx+1];
    return ou[calc(st[fx][k],st[fy-(1<<k)+1][k])];
}
vector<int> ovo1[N];
vector<int> del1[N];
vector<int> ovo2[N];
vector<int> del2[N];
multiset<int> a[N],b[N];
int gen[N],sum[N],ans[N];
void dfs2(int x,int fa){
    int ok=0;
    for(int i=Head[x];i!=-1;i=Next[i]){
        if(V[i]!=fa){
            ok++;
            dfs2(V[i],x);
            if(sum[gen[x]]<sum[gen[V[i]]]){
                gen[x]=gen[V[i]];
            }
        }
    }

    if(gen[x]==0)gen[x]=x;
    for(int i=Head[x];i!=-1;i=Next[i]){
        if(V[i]!=fa&&gen[V[i]]!=gen[x]){
            for(multiset<int>::iterator it=a[gen[V[i]]].begin();it!=a[gen[V[i]]].end();it++){
                a[gen[x]].insert(*it);
                sum[gen[x]]++;
            }
            a[gen[V[i]]].clear();
            for(multiset<int>::iterator it=b[gen[V[i]]].begin();it!=b[gen[V[i]]].end();it++){
                b[gen[x]].insert(*it);
                sum[gen[x]]++;
            }
            b[gen[V[i]]].clear();
        }
    }

    int len=ovo1[x].size();
    for(int i=0;i<len;i++){
        a[gen[x]].insert(ovo1[x][i]);
        sum[gen[x]]++;
    }
    len=ovo2[x].size();
    for(int i=0;i<len;i++){
        b[gen[x]].insert(ovo2[x][i]);
        sum[gen[x]]++;
    }

    len=del2[x].size();
    for(int i=0;i<len;i++){
        b[gen[x]].erase(b[gen[x]].find(del2[x][i]));
        sum[gen[x]]--;
    }

    ans[x]=a[gen[x]].count(w[x]+depth[x])+b[gen[x]].count(w[x]-depth[x]);

    len=del1[x].size();
    for(int i=0;i<len;i++){
        a[gen[x]].erase(a[gen[x]].find(del1[x][i]));
        sum[gen[x]]--;
    }
}
int main(){
    memset(Head,-1,sizeof(Head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    ST();
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=m;i++){
        int s,t;
        scanf("%d%d",&s,&t);
        int lca=LCA(s,t);
        if(lca==0){
            printf("BUG\n");
        }
        ovo1[s].push_back(depth[s]);
        ovo2[t].push_back(depth[s]-depth[lca]*2);
        del1[lca].push_back(depth[s]);
        del2[lca].push_back(depth[s]-depth[lca]*2);
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    printf("\n");
}