题解：P14755 西安之泪

314zbl · 2025-12-14 18:58:42 · 题解

题解：P14755 西安之泪

题目大意

给定一棵 n 个节点的树，每个节点初始权值为 0。可以进行最多 3n 次操作：

指定根节点 r 和操作节点 u。
在以 r 为根的树中，将 u 子树内的所有节点权值异或上 u。

要求构造操作序列，使得最终每个节点 i 的权值为 i。

思路

瞪眼法

性质：每次操作实际上是以某个节点 r 为根，对节点 u 的子树进行集体异或。但要注意，不同的根选择会导致同一个节点 u 的子树包含的节点不同。
目标转换：最终每个节点 i 需要被异或上 i 一次（因为 0 \oplus i = i），且不能受到其他节点的干扰。
思路：对于每个节点 u，我们构造一组操作，使得这组操作的效果是：
- 节点 u 被异或上 u 一次
- 其他所有节点不被这个 u 的操作影响
  构造方法
  
  对于每个节点 u，设其度数为 k（邻居个数）：
如果 k 是奇数：
- 对 u 的每个邻居 v，进行一次操作 (r = v, u = u)。
如果 k 是偶数：
- 先进行一次操作 (r = u, u = u)。
- 再对 u 的每个邻居 v，进行一次操作 (r = v, u = u)。
  正确性证明
  
  考虑任意节点 u 的构造：
对 u 本身的影响：
- 当 k 为奇数时，u 会出现在每个邻居为根的 u 子树中，总共 k 次（奇数次）异或 u，效果等价于异或一次。
- 当 k 为偶数时，先以 u 为根（包含 u 自己），再以每个邻居为根，共 k+1 次（奇数次），效果等价于异或一次。
对其他节点 x 的影响：
- 设 x \neq u，v_0 是 u 到 x 路径上 u 的第一个邻居。
- 当以 v_0 为根时，x 不在 u 的子树中。
- 当以 u 的其他邻居为根时，x 在 u 的子树中
- 因此 x 被异或的次数为：
总体效果：
- 每个节点 u 的构造只让 u 自己被异或上 u。
- 不同节点的操作相互独立，最终每个节点 i 的权值为 i。

代码实现

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

时间复杂度每次 O(n)，能很容易地过。

题解：P14755 西安之泪

题解：P14755 西安之泪

题目大意

思路

瞪眼法

构造方法

正确性证明

代码实现