RT

是不是我写法上的问题？就算在dfs暴力一遍叶子节点最后的答案也是错误的.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e5+10;

int dep[M],sz[M],fa[M],hev[M],tp[M],dfn[M];
int w[M],w1[M],ans[M];
vector<int>p[M];

int dfs1(int u,int d)
{
    dep[u]=d;sz[u]=0;hev[u]=-1;
    vector<int>::iterator i;
    for(i=p[u].begin();i!=p[u].end();++i)
        {
            int to=*i;
            if(to==fa[u]) continue;
            fa[to]=u;
            sz[u]+=dfs1(to,d+1);
            if(hev[u]==-1 || sz[to]>sz[hev[u]]) hev[u]=to;
        }
    return sz[u];
}

int tot;
void dfs2(int u,int t)
{
    tp[u]=t;
    dfn[u]=++tot;
    w1[dfn[u]]=w[u];
    if(hev[u]!=-1) dfs2(hev[u],t);
    vector<int>::iterator i;
    for(i=p[u].begin();i!=p[u].end();++i)
        {
            int to=*i;
            if(to==fa[u] || to==hev[u]) continue;
            dfs2(to,to);
        }
    return;
}

long long mx,sum;
long long c[M];
void dfs(int u)
{
    int k=++c[w1[dfn[u]]];
    if(k>mx)
    {
        mx=k;
        sum=w1[dfn[u]];
    }else if(k==mx) sum+=w1[dfn[u]];
    vector<int>::iterator i;
    for(i=p[u].begin();i!=p[u].end();++i)
        {
            int to=*i;
            if(to==fa[u] || to==hev[u])
                {
                    continue;
                }
            dfs(to);
        }
    if(hev[u]==-1) 
    ans[u]=w1[dfn[u]];
}

void init(int u)
{
    --c[w1[dfn[u]]];
    vector<int>::iterator i;
    for(i=p[u].begin();i!=p[u].end();++i)
        {
            int to=*i;
            if(to!=fa[u])
                {
                    init(to);
                }
        }
}

void dfs3(int u)
{
    vector<int>::iterator i;
    for(i=p[u].begin();i!=p[u].end();++i)
        {
            int to=*i;
            if(to==fa[u] || to==hev[u]) continue;
            dfs(to);
            init(to);
            sum=mx=0;
        }
    if(hev[u]!=-1) dfs3(hev[u]);
    dfs(u);
    ans[u]=sum;
}

int n;

signed main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>w[i];

    for(int i=1;i<n;++i)
        {
            int u,v;
            cin>>u>>v;
            p[u].push_back(v);
            p[v].push_back(u);
        }

    dfs1(1,0);
    dfs2(1,0);
    // for(int i=1;i<=n;++i)
        dfs3(1);
    
    for(int i=1;i<=n;++i)
        cout<<ans[dfn[i]]<<endl;
    
    return 0;
}