第二道黑题，想了一周终于想出来了，小激动。

main

主要思路：根据字典序定义，从小到大把每个数往小里放就一定行，于是从每个数开始搜索，找编号最小的合法终点。

补充一些细节：

只要确定了每个点的出边删除顺序，就一定有合法解。

在任何有至少一条边的状态中，设 $n$ 为点数， $e$ 为边数，一定有 $e\leqslant{n-1}$ ，于是一定有两个点都把连接他们的边当做他们第一个要删的边，最终删的一边不剩。

code

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>//75760209
#include<ctime>
#include<climits>
#include<random>
#include<algorithm>
#include<map>
#include<queue>
#define fru(i,j,k) for(register int i=j;i<=k;i++)//for_register_up
#define frd(i,j,k) for(register int i=j;i>=k;i--)//for_register_down
#define pc(charx) putchar(charx)
#define finfout(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using ll = long long;
namespace usegetin{
    char c=' ';
    inline int in()
    {
        ll x=0;bool w=false;
        while(!isdigit(c))
        {
            w|=c=='-';
            c=getchar();
        }
        while(isdigit(c))
        {
            x=(x<<1)+(x<<3)+(c^48);
            c=getchar();
        }
        return w?-x:x;
    }
    template<typename ty>
    void out(ty x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)out(x/10);
        putchar(x%10+48);
    }
}
using usegetin::in;using usegetin::out;
using namespace std;
const int maxn=2012;
int t,n;
struct edg
{
    int next,to;
}edge[maxn<<1];
int head[maxn],cnt=2;
struct node
{
    int hd,bk,cnt,fa[maxn];
    bool eto[maxn],ebk[maxn];
    void cl(void)
    {
        hd=bk=cnt=0;
        fru(i,1,n)fa[i]=i,eto[i]=ebk[i]=false;
    }
    inline int findfa(int dc)
    {
        return dc==fa[dc]?dc:(fa[dc]=findfa(fa[dc]));
    }
}nl[maxn];
int ml[maxn];
inline void getin(int a,int b)
{
    edge[cnt]=(edg){head[a],b};
    head[a]=cnt++;
    nl[b].cnt++;
}
int ans;
void dfs(int dc,int lst)
{
    if(lst&&(!nl[dc].bk||nl[dc].bk==lst))
    {
        if(!nl[dc].ebk[lst]&&!(nl[dc].cnt>1&&nl[dc].hd&&nl[dc].findfa(nl[dc].hd)==nl[dc].findfa(lst)))
        {
            ans=min(ans,dc);
        } 
    }
    int v;
    for(register int j=head[dc];j;j=edge[j].next)
    if(lst^(v=edge[j].to))
    {
        if(lst)
        { 
            if(nl[dc].findfa(lst)==nl[dc].findfa(v))continue;
            if(nl[dc].ebk[lst]||nl[dc].eto[v])continue;
            if(nl[dc].hd&&nl[dc].bk&&nl[dc].findfa(nl[dc].hd)==nl[dc].findfa(lst)&&nl[dc].findfa(v)==nl[dc].findfa(nl[dc].bk)&&nl[dc].cnt>1)continue;
            dfs(v,dc);
        }
        else
        {
            if(nl[dc].hd&&nl[dc].hd^v)continue;
            if(nl[dc].eto[v])continue;
            if(nl[dc].bk&&nl[dc].cnt>0&&nl[dc].findfa(nl[dc].bk)==nl[dc].findfa(v))continue;
            dfs(v,dc);
        }
    }
}
bool dfs1(int dc,int lst)
{
    if(dc==ans)
    {
        nl[dc].bk=lst;
        nl[dc].ebk[lst]=true;
        nl[dc].cnt--;
        return true;
    }
    int v;
    for(register int j=head[dc];j;j=edge[j].next)
    if(lst^(v=edge[j].to)&&dfs1(v,dc))
    {
        if(!lst)
        {
            nl[dc].eto[v]=true;
            nl[dc].hd=v;
        }
        else 
        {
            nl[dc].ebk[lst]=nl[dc].eto[v]=true;
            nl[dc].fa[nl[dc].findfa(lst)]=nl[dc].findfa(v);
            nl[dc].cnt--;
        }
        return true;
    }
    return false;
}
int main()
{
    t=in();
    int t1,t2;
    while(t--)
    {
        cnt=2;
        memset(head,0,sizeof head);
        n=in();
        fru(i,1,n)nl[i].cl();
        fru(i,1,n)ml[i]=in();
        fru(i,1,n-1)
        {
            t1=in();t2=in();
            getin(t1,t2);
            getin(t2,t1);
        }
        if(n==1)
        {
            puts("1");
        }
        else
        {
            fru(i,1,n)
            {
                ans=n+1;
                dfs(ml[i],0);
                dfs1(ml[i],0);
                out(ans);pc(' ');
            }
            pc('\n');
        }
    }
    return 0; 
}

题解_[CSP-S2019] 树上的数

main

code