Language: C++

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,tot,rt,d[N],ans[N],sa,sb,f[N][2],g[N][2],head[N],nex[N<<1],to[N<<1];
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
vector<int>v[3];
int get(int x)
{
    int ans=v[x].back();v[x].pop_back();return ans;
}
void dfs1(int u,int fa)
{
    f[u][0]=1;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        dfs1(v,u);
        f[u][0]+=f[v][1];
        f[u][1]+=f[v][0];
    }
}
void dfs2(int u,int fa)
{
    if(f[u][0]>=v[1].size()&&f[u][1]>=v[2].size()||f[u][0]>=v[2].size()&&f[u][1]>=v[1].size())
        rt=u,sa=f[u][0],sb=f[u][1];
    g[u][0]=f[u][0];g[u][1]=f[u][1];
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        f[u][0]-=f[v][1];
        f[u][1]-=f[v][0];
        f[v][0]+=f[u][1];
        f[v][1]+=f[u][0];
        dfs2(v,u);
        f[v][0]-=f[u][1];
        f[v][1]-=f[u][0];
        f[u][0]+=f[v][1];
        f[u][1]+=f[v][0];
    }
}
int k;
void dfs(int u,int fa,int dep)
{
    if(dep==k)
    {
        if(v[1].size())
            ans[u]=v[1].back(),v[1].pop_back();
        else  if(v[0].size()) ans[u]=v[0].back(),v[0].pop_back();
        else
        {
            printf("-1\n");exit(0);
        }
    }
    else
    {
        if(v[2].size())
            ans[u]=v[2].back(),v[2].pop_back();
        else  if(v[0].size()) ans[u]=v[0].back(),v[0].pop_back();
        else
        {
            printf("-1\n");exit(0);
        }
    }
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        dfs(v,u,dep^1);
    }
}
int p[N];
void add(int u,int s)
{
    if(s==k) ans[u]=get(1);
    else ans[u]=get(2);
}
void solve(int u,int fa,int dep)
{
    if(dep==1)
    {
        if(d[u]!=1)
        {
            add(u,dep&1);
        }
    }
    else if(dep==2)
    {
        ans[u]=get(0);
    }
    else
    {
        add(u,dep&1);
    }
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        solve(v,u,dep+1);
    }
}
void solve(int rt)
{
    if(g[rt][0]<=v[1].size()&&g[rt][1]<=v[2].size()) k=0;
    else k=1;
    solve(rt,0,0);
    for(int i=1;i<=n;i++)
    {
        if(!ans[i])
        {
            if(v[0].size()) ans[i]=get(0);
            else if(v[1].size()) ans[i]=get(1);
            else ans[i]=get(2);
        }
        printf(i==n?"%d\n":"%d ",ans[i]);
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=nex[j])
        {
            int v=to[j];
            if(d[v]==1) g[i][1]--;
            g[i][0]-=d[v]-1,p[i]+=d[v]-1;
        }
        if(p[i]>v[0].size()) continue;
        if(g[i][0]<=v[1].size()&&g[i][1]<=v[2].size()||g[i][1]<=v[1].size()&&g[i][0]<=v[2].size())
        {
            solve(i);exit(0);
        }
    }
    assert(0);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        v[i%3].push_back(i);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);
        d[u]++;d[v]++;
    }
    dfs1(1,0);
    dfs2(1,0);
    if(rt==0)
    {
        solve();
        return 0;
    }
    if(sa>=v[1].size()&&sb>=v[2].size()) k=0;
    else k=1;
    dfs(rt,0,0);
    for(int i=1;i<=n;i++)
        printf(i==n?"%d\n":"%d ",ans[i]);
}


Compiler output:
a.cc:71:6: error: redefinition of 'void add(int, int)'
   71 | void add(int u,int s)
      |      ^~~
a.cc:5:6: note: 'void add(int, int)' previously defined here
    5 | void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
      |      ^~~