题解

#include<bits/stdc++.h>
#define maxn 2005
using namespace std;

struct n
{
    int f[maxn],x[maxn],r[maxn];
    int g(int a) {return f[a]==a?a:f[a]=g(f[a]);}
    int i,l,c;
} p[maxn];
int e[maxn<<1],t[maxn<<1],s[maxn],j=1;
int m[maxn],k[maxn],o;
int q;

auto h = [&](int a, int b)
{
    e[++j]=s[a];
    s[a]=j,t[j]=b;
};

int u(int a,int b)
{
    int c=1e9,d;
    if(b)
    {
        if(!p[a].l||b/2==p[a].l)
        {
            if(!p[a].x[b/2]&&(!p[a].i||(p[a].g(b/2)!=p[a].g(p[a].i))||p[a].c==1)) c=min(c,a),k[a]=0;
        }
    }
    for(int i=s[a];i;i=e[i])
    {
        int y=t[i]; if(b/2==i/2) continue;
        if(!b&&(!p[a].i||p[a].i==i/2))
        {
            if(!p[a].l||(p[a].g(i/2)!=p[a].g(p[a].l))||p[a].c==1)
            {
                if(p[a].r[i/2]) continue;
                d=u(y,i);
                if(d<c) c=d,k[a]=y;
            }
        }
        else
        {
            if(b/2==p[a].l||i/2==p[a].i||p[a].g(b/2)==p[a].g(i/2)||p[a].x[b/2]||p[a].r[i/2]) continue;
            if(!p[a].l||!p[a].i)
            {
                d=u(y,i);
                if(d<c) c=d,k[a]=y;
            }
            else
            {
                int ax=p[a].g(b/2),ay=p[a].g(i/2);
                int bx=p[a].g(p[a].i),by=p[a].g(p[a].l);
                if(ax>ay) swap(ax,ay); if(bx>by) swap(bx,by);
                if((bx!=ax||by!=ay)||p[a].c==2)
                {
                    d=u(y,i);
                    if(d<c) c=d,k[a]=y;
                }
            }
        }
    }
    return c;
}

void v(int a,int b)
{
    if(!k[a])
    {
        p[a].l=b/2;
        return;
    }
    for(int i=s[a];i;i=e[i])
    {
        int y=t[i]; if(y!=k[a]) continue;
        if(!b) p[a].i=i/2;
        else
        {
            p[a].f[p[a].g(b/2)]=p[a].g(i/2);
            p[a].r[i/2]=1,p[a].x[b/2]=i/2;
            p[a].c--;
        }
        v(y,i);
    }
};

int main()
{

    auto w = [&]()
    {
        for(int i=1;i<=o;i++)
        {
            s[i]=0;
            memset(p[i].f,0,sizeof(p[i].f));
            memset(p[i].r,0,sizeof(p[i].r));
            memset(p[i].x,0,sizeof(p[i].x));
            p[i].c=p[i].i=p[i].l=0;
        }
        j=1;
    };

    cin>>q;
    while(q--)
    {
        cin>>o;
        w();
        for(int i=1;i<=o;i++) cin>>m[i];
        for(int i=1,a,b;i<o;i++) cin>>a>>b,h(a,b),h(b,a);
        for(int a=1;a<=o;a++)
            for(int i=s[a];i;i=e[i])
                p[a].f[i/2]=i/2,p[a].c++;
        for(int z=1;z<=o;z++)
        {
            cout<<u(m[z],0)<<" ";
            v(m[z],0);
        }
        cout<<"\n";
    }
    return 0;
}

第一道黑题，激动到内牛满面