西安之泪题解

wsx10 · 2025-12-14 18:28:59 · 题解

由于最终每个点 i 的权值应当是 i。故对每个节点 u 设计一组操作，使得这组操作执行完后只有 u 被异或了一次 u，其他点不受影响即可。

考虑点 u。记其邻居有 d 个，分别为 v_1, v_2, \dots, v_d。利用求树的重心时两次 DFS 的思想，考虑以邻居为根，这样能够影响到点 u。我们考虑以下策略：

对每个邻居 v_i 执行操作 (v_i, u)。这是因为以 v_i 为根时，u 的子树包含 u 以及所有不在 v_i 另一侧子树内的节点。
如果 d 是偶数，需要额外执行一次 (u, u)。这是因为以 u 为根时，u 的子树就是整棵树。

上述策略的正确性可以通过计算任意节点 w 被异或的次数显然得到。

下面对操作数的上界进行验证。不妨记 E 为度数为偶数的节点个数。由 d_u = \deg(u) 知总操作数为 K = \sum_{u=1}^n d_u + E = 2(n-1) + E 次。当 n>1 时，树至少有两个叶子，故 E \le n-2，于是 K \le 2(n-1) + (n-2) \leq 3n。又 n=1 时，K=1 \leq 3。故该策略的操作次数总数可以被接受。

按上述构造直接输出即可，时间复杂度 O(n)。代码如下：

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vector<vector<int> > adj(n+1);
        for(int i=1;i<n;i++)
        {
            int u,v;
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<pii> ops;
        for(int i=1;i<=n;i++)
        {
            for(auto v:adj[i]) ops.emplace_back(v,i);
            if(adj[i].size()%2==0) ops.emplace_back(i,i);
        }
        cout<<ops.size()<<'\n';
        for(auto [r,u]:ops){
            cout<<r<<' '<<u<<'\n';
        }
    }
    return 0;
}

西安之泪 题解

西安之泪题解