最长题解，ai写注释（700+行）

我128.01MB,超越了0.00%的人内存

# include <bits/stdc++.h>
typedef unsigned long long ull;

using  namespace  std ;

// 定义最大节点数量，用于预先分配足够的内存空间
// 可根据实际问题规模调整此值

const int Maxn = 3e3;

// 边的结构体，用于构建邻接表存储图的边信息

struct Edge
{
    int to;  // 边的终点，即这条边指向的节点编号

    Edge *nxt;  // 指向下一条邻接边的指针，用于构建链表
};

// 边池，是一个数组，用于存储所有的边
// 预先分配一定数量的边空间，避免频繁的内存分配和释放操作，提高效率

Edge pool[ Maxn * 2 + 5];

// 邻接表数组，G[i] 指向节点 i 的第一条邻接边
// 通过链表的方式存储每个节点的所有邻接边

Edge *G[ Maxn + 5], *ecnt;

// 向图中添加一条无向边 (u, v)
// 由于是无向图，需要添加两条有向边 (u, v) 和 (v, u)

inline void addedge
(int u, int v)
{
    // 从边池中取出一条新的边
    // ecnt 指针初始指向边池的起始位置，每次取边后向后移动
    
    Edge *p = ++ ecnt;
    
    // 设置边的终点为 v
    
    p -> to = v;
    
    // 将新边插入到节点 u 的邻接表头部
    // 采用头插法，方便新边的插入操作
    
    p -> nxt = G[ u];
    G[ u] = p;
}

// 节点数量，即图中节点的总数

int N;

// num[i] 表示数字 i 所在的节点编号
// 用于记录每个数字对应的节点位置

int num[ Maxn + 5];

// 链表相关数组，用于模拟边的删除顺序和状态
// pre[u][v] 表示节点 u 到节点 v 的边的前一条边
// 在边的删除顺序链表中，用于确定当前边的前一个位置

int pre[ Maxn + 5][ Maxn + 5];

// nxt[u][v] 表示节点 u 到节点 v 的边的后一条边
// 在边的删除顺序链表中，用于确定当前边的后一个位置

int nxt[ Maxn + 5][ Maxn + 5];

// head[u][v] 表示以节点 u 到节点 v 的边为起点的链表的头节点
// 方便快速定位链表的起始位置

int head[ Maxn + 5][ Maxn + 5];

// tail[u][v] 表示以节点 u 到节点 v 的边为起点的链表的尾节点
// 方便快速定位链表的结束位置

int tail[ Maxn + 5][ Maxn + 5];

// len[u][v] 表示以节点 u 到节点 v 的边为起点的链表的长度
// 记录链表中边的数量，用于判断链表的完整性

int len[ Maxn + 5][ Maxn + 5];

// deg[i] 表示节点 i 的度数
// 即与节点 i 相连的边的数量

int deg[ Maxn + 5];

// 清空图和链表的相关信息，为处理新的测试用例做准备
// 在每次处理新的测试用例前调用，确保数据的初始状态正确

inline void clear
()
{
    // 重置边池指针，使其指向边池的起始位置
    
    ecnt = pool + 0;
    
    // 清空每个节点的邻接表
    
    for 
    (int i = 1; i <= N; i++)
    {
        // 将每个节点的第一条邻接边指针置为 NULL，表示该节点没有邻接边
        
        G[ i] = NULL;
    }
    
    // 初始化链表的相关信息
    // 将所有链表的长度、前后指针、头节点和尾节点都置为 0
    
    for 
    (int i = 1; i <= N + 1; i++)
    {
        
        for 
        (int j = 1; j <= N + 1; j++)
        {
            // 将所有链表的长度置为 0
            
            len[ i][ j] = 0;
            
            // 将所有链表的前指针置为 0
            
            pre[ i][ j] = 0;
            
            // 将所有链表的后指针置为 0
            
            nxt[ i][ j] = 0;
            
            // 将所有链表的头节点置为 0
            
            head[ i][ j] = 0;
            
            // 将所有链表的尾节点置为 0
            
            tail[ i][ j] = 0;
        }
    }
    
    // 初始化每个节点的度数为 0
    
    for 
    (int i = 1; i <= N; i++)
    {
        deg[ i] = 0;
    }
}

// 记录最小的目标节点编号
// 在深度优先搜索过程中，不断更新该值，找到最小的满足条件的节点

int minp;

// 深度优先搜索函数，用于找到合适的边删除顺序以确定最小的目标节点
// u 表示当前搜索的节点，fa 表示当前节点的父节点

void DFS1
(int u, int fa)
{
    // 获取当前边所在链表的头节点和尾节点
    
    int st = head[ u][ fa];
    int ed = tail[ u][ fa];
    
    // 如果 fa 为 N + 1，表示当前是搜索的起点
    // 因为在初始化和逻辑中，N + 1 作为特殊标记表示起始状态
    
    if 
    (fa == N + 1)
    {
        // 遍历节点 u 的所有邻接边
        
        for 
        (Edge *p = G[ u]; p != NULL; p = p->nxt)
        {
            int v = p->to;
            int t1 = head[ u][ v], t2 = tail[ u][ v];
            
            // 如果这条边不满足作为起始边的条件，跳过
            // 条件判断：如果该边所在链表的头节点不是自身
            // 或者该边所在链表的尾节点已经被标记且链表长度小于节点 u 的度数
            
            if 
            (t1 != v || 
            (pre[ u][ fa] == t2 && len[ u][ t1] < deg[ u]))
            {
                continue;
            }
            
            // 递归搜索下一个节点
            // 以 v 为新的当前节点，u 为其父节点继续搜索
            
            DFS1
            (v, u);
        }
    }
    
    else
    {
        
        // 如果当前边是链表的尾节点
        
        if 
        (fa == ed)
        {
            // 判断当前节点是否可以作为结束点
            // 条件判断：如果该节点的最后一条未删边还未指定
            // 且（该节点的下一条边不是链表头节点或者链表长度等于节点 u 的度数）
            
            if 
            (pre[ u][ N + 1] == 0 && 
            (nxt[ u][ N + 1] != st || len[ u][ st] == deg[ u]))
            {
                // 更新最小目标节点编号
                
                minp = min(minp, u);
            }
            
            // 遍历节点 u 的所有邻接边
            
            for 
            (Edge *p = G[ u]; p != NULL; p = p->nxt)
            {
                int v = p->to;
                int t1 = head[ u][ v], t2 = tail[ u][ v];
                
                // 如果这条边不满足连接条件，跳过
                // 条件判断：如果两条边已经在同一个链表中，或者该边不是起始边
                // 或者该边已经被指定为下一条边
                
                if 
                (st == t1 || t1 != v || nxt[ u][ N + 1] == v)
                {
                    continue;
                }
                
                // 如果边连接后形成的环长度不满足要求，跳过
                // 条件判断：如果边连接后形成的环的长度小于节点 u 的度数
                
                if 
                (nxt[ u][ N + 1] == st && pre[ u][ N + 1] == t2 && len[ u][ st] + len[ u][ t1] < deg[ u])
                {
                    continue;
                }
                
                // 递归搜索下一个节点
                // 以 v 为新的当前节点，u 为其父节点继续搜索
                
                DFS1
                (v, u);
            }
        }
        else
        {
            // 按照链表顺序继续搜索下一个节点
            // 找到当前边的下一条边对应的节点继续搜索
            
            DFS1
            (nxt[ u][ fa], u);
        }
    }
}

// 合并以节点 u 为起点，分别以 st 和 ed 为边的两个链表
// 用于将两个边的删除顺序链表合并成一个

inline void merge
(int u, int st, int ed)
{
    // 获取两个链表的头节点和尾节点
    
    int t1 = head[ u][ st];
    int t2 = tail[ u][ ed];
    
    // 连接两个链表
    // 将 st 边的下一条边设置为 ed 边
    // ed 边的前一条边设置为 st 边
    
    nxt[ u][ st] = ed;
    pre[ u][ ed] = st;
    
    // 更新链表中每个节点的头节点和尾节点信息
    // 遍历以 t1 为头节点的链表，将其中每个节点的头节点和尾节点更新为合并后链表的头节点和尾节点
    
    for 
    (int i = t1; i != 0 && i != N + 1;)
    {
        head[ u][ i] = t1;
        tail[ u][ i] = t2;
        i = nxt[ u][ i];
    }
    
    // 更新合并后链表的长度
    // 将两个链表的长度相加
    
    len[ u][ t1] += len[ u][ ed];
}

// 深度优先搜索函数，用于更新链表以确定最终的边删除顺序
// u 表示当前搜索的节点，fa 表示当前节点的父节点

bool DFS2
(int u, int fa)
{
    // 如果当前节点是最小的目标节点
    
    if 
    (u == minp)
    {
        // 将当前边标记为最后一条边
        // 表示找到了满足条件的边删除顺序的终点
        
        pre[ u][ N + 1] = fa;
        nxt[ u][ fa] = N + 1;
        
        // 返回 true
        
        return true;
    }
    
    // 获取当前边所在链表的头节点和尾节点
    
    int st = head[ u][ fa];
    int ed = tail[ u][ fa];
    
    // 如果 fa 为 N + 1，表示当前是搜索的起点
    
    if 
    (fa == N + 1)
    {
        // 遍历节点 u 的所有邻接边
        
        for 
        (Edge *p = G[ u]; p != NULL; p = p->nxt)
        {
            int v = p->to;
            int t1 = head[ u][ v];
            int t2 = tail[ u][ v];
            
            // 如果这条边不满足作为起始边的条件，跳过
            // 条件判断：如果该边所在链表的头节点不是自身
            // 或者该边所在链表的尾节点已经被标记且链表长度小于节点 u 的度数
            
            if 
            (t1 != v || 
            (pre[ u][ N + 1] == t2 && len[ u][ t1] < deg[ u]))
            {
                continue;
            }
            
            // 递归搜索下一个节点
            
            if 
            (DFS2
            (v, u))
            {
                // 将当前边标记为起始边
                // 表示找到了满足条件的边删除顺序的起点
                
                nxt[ u][ N + 1] = v, pre[ u][ v] = N + 1;
                
                // 返回 true
                
                return true;
            }
        }
    }
    else
    {
        // 如果当前边是链表的尾节点
        
        if (fa == ed)
        {
            // 遍历节点 u 的所有邻接边
            
            for 
            (Edge *p = G[ u]; p != NULL; p = p->nxt)
            {
                int v = p->to;
                int t1 = head[ u][ v];
                int t2 = tail[ u][ v];
                
                // 如果这条边不满足连接条件，跳过
                // 条件判断：如果两条边已经在同一个链表中，或者该边不是起始边
                // 或者该边已经被指定为下一条边
                
                if 
                (st == t1 || t1 != v || nxt[ u][ N + 1] == v)
                {
                    continue;
                }
                
                // 如果边连接后形成的环长度不满足要求，跳过
                // 条件判断：如果边连接后形成的环的长度小于节点 u 的度数
                
                if 
                (nxt[ u][ N + 1] == st && pre[ u][ N + 1] == t2 && len[ u][ st] + len[ u][ t1] < deg[ u])
                {
                    continue;
                }
                
                // 递归搜索下一个节点
                
                if 
                (DFS2
                (v, u)) 
                {
                    
                    // 合并两个链表
                    // 将当前边所在链表和 v 边所在链表合并
                    
                    merge
                    (u, fa, v);
                    
                    // 返回true
                    
                    return true;
                }
            }
        }
        else
        {
            
            // 按照链表顺序继续搜索下一个节点
            // 找到当前边的下一条边对应的节点继续搜索
            
            DFS2
            (nxt[ u][ fa], u);
        }
    }
    
    // 返回 false , 表示上面在没有返回 true 的情况下返回
    
    return false;
}

// 并查集类，用于优化边的合并和查找操作
// 并查集可以高效地判断两个节点是否连通，以及合并两个连通分量

class UnionFind
{

// 使用vector 来更容易添加
private:
    // parent[i] 表示节点 i 的父节点
    // 在并查集中，通过不断查找父节点找到根节点

    vector<int> parent;

    // rank[i] 表示以节点 i 为根的树的高度
    // 用于优化合并操作，将高度较小的树合并到高度较大的树中

    vector<int> rank;
public:
    // 构造函数，初始化并查集
    // n 表示节点的数量

    UnionFind
    (int n)
    {
        // 调整 parent 和 rank 数组的大小
        
        parent.resize
        (n + 1);
        rank.resize
        (n + 1, 0);
        
        // 初始时每个节点的父节点是它自己
        // 表示每个节点都是一个独立的连通分量
        
        for 
        (int i = 1; i <= n; i ++)
        {
            parent[ i] = i;
        }
    }

    // 查找节点 x 所在集合的根节点，并进行路径压缩
    // 路径压缩可以使查找操作的时间复杂度接近常数

    int find
    (int x)
    {
        if 
        (parent[ x] != x)
        {
            // 递归查找父节点，并将当前节点的父节点直接设置为根节点
            
            parent[ x] = find(parent[ x]);
        }
        return parent[ x];
    }

    // 合并节点 x 和节点 y 所在的集合

    void unite
    (int x, int y)
    {
        // 找到 x 和 y 所在集合的根节点
        
        int rootX = find
        (x);
        int rootY = find
        (y);
        
        if 
        (rootX != rootY)
        {
            // 根据树的高度进行合并
            
            if 
            (rank[ rootX] < rank[ rootY])
            {
                parent[ rootX] = rootY;
            }
            else if 
            (rank[ rootX] > rank[ rootY])
            {
                parent[ rootY] = rootX;
            }
            else
            {
                // 如果两棵树高度相同，将其中一棵树的根节点指向另一棵树的根节点，并更新高度
                
                parent[ rootY] = rootX;
                rank[ rootX] ++;
            }
        }
    }

    // 判断节点 x 和节点 y 是否在同一个集合中

    bool connected
    (int x, int y)
    {
        // 如果两个节点的根节点相同，则它们在同一个集合中
        
        return find
        (x) == find
        (y);
    }
};

// 快读 int 类型的变量

int r
()
{
    short f = 1;
    int x = 0;
    
    char c = getchar
    ();
    
    while 
    (c < '0' || c > '9')
    {
        
        if 
        (c == '-')
        {
            f = -1;
        }
        
        c = getchar
        ();
    }
    
    int dey = (3 << 4);
    
    while 
    (c >= '0' && c <= '9')
    {
        
        x = (x << 1) + (x << 3) + (c ^ dey);
        
        c = getchar
        ();
    }
    
    return x * f;
}

void solve
()
{
    // 读取节点数量
    
    N = r();
    
    // 清空图和链表的相关信息
    // 为处理新的测试用例做准备
    
    clear();
    clear();
    
    // 读取每个数字所在的节点编号
    
    for 
    (int i = 1; i <= N; i ++)
    {
        num[ i] = r();
    }
    
    // 创建并查集对象
    // 用于处理节点的连通性问题
    
    UnionFind uf(N);
    
    // 读取边的信息并构建图
    
    for 
    (int i = 1; i < N; i ++)
    {
        int u, v;
        
        u = r();
        v = r();
        
        // 添加无向边
        // 由于是无向图，需要添加两条有向边
        
        addedge(u, v);
        addedge(v, u);
        
        // 更新节点的度数
        // 每条边会使两个端点的度数加 1
        
        ++ deg[ u];
        ++ deg[ v];
        
        // 初始化链表信息
        // 初始时每个边所在的链表长度为 1，前后指针为 0，头节点和尾节点为自身
        
        pre[ u][ v] = 0;
        pre[ v][ u] = 0;
        nxt[ u][ v] = 0;
        nxt[ v][u] = 0;
        
        head[ u][ v] = v;
        tail[ u][ v] = v;
        
        head[ v][ u] = u;
        tail[ v][ u] = u;
        
        len[ u][ v] = 1;
        len[ v][ u] = 1;
        
        // 合并节点 u 和节点 v 所在的集合
        // 表示 u 和 v 是连通的
        
        uf.unite(u, v);
    }
    
    // 如果只有一个节点，直接输出该节点编号
    
    if
    (N == 1)
    {
        printf("%d\n", num[1]);
        
        return;
    }
    
    // 对于每个数字所在的节点，进行深度优先搜索
    
    for
    (int i = 1; i <= N; i ++)
    {
        // 初始化最小目标节点编号为 N + 1
        // 因为 N + 1 是一个特殊标记，用于确保后续更新时可以正确比较
        
        minp = N + 1;
        
        // 第一次深度优先搜索，找到最小目标节点
        // 从数字 i 所在的节点开始搜索
        
        DFS1(num[ i], N + 1);
        
        // 第二次深度优先搜索，更新链表以确定最终的边删除顺序
        // 同样从数字 i 所在的节点开始搜索
        
        DFS2(num[ i], N + 1);
        
        // 输出最小目标节点编号
        // 根据是否是最后一个数字决定输出换行符还是空格
        
        printf("%d%c", minp, (i == N) ? '\n' : ' ');
    }    
}

int  main ( )
{
    int T;
    
    // 读取测试用例的数量
    
    T = r();
    
    while
    (T --)
    {
        solve();
    }
    
    return  0;
}