题解：P14755 西安之泪

Norfor · 2025-12-16 19:21:19 · 题解

题目大意

给你一颗大小为 n 的树，节点 i 的点权为 a_i，每个点的初始点权都为 0，可以执行以下操作至多 3n 次。

选择根节点 r 和操作点 u。
使得以 r 为根，u 节点的子树上的所有节点的点权异或上 u。

使得对任意的 i，都有 a_i=i。

解题思路

如果对于任意节点 i 都有一套操作能达成仅将节点 i 从 a_i=0 变为 a_i=i 且其他节点点权都不变，那么这题就容易解决了。
观察到这题操作次数限制为 3n，这个限制可能具有一定指向性，例如每条边操作一次总共会操作 n-1 次，每个点操作一次总共会操作 n 次。
考虑对于操作 r，u 产生的效果：
1. 若 r=u，那么产生的效果就是将整棵树的点权都异或上 u。
2. 否则，我们先将 u 点从这颗树上去掉，记 deg[u] 为 u 点的度，那么此时这颗树就变为了 deg[u] 个连通块，只有 r 所在连通块的点不会被异或，其余点皆会被异或上 u。
结合以上两点我们的思路很容易导向在操作节点 u 时，让每个与 u 相连的点都做一次根节点，便可以得到以下结果：
1. 若 deg[u] 为奇数，则节点 u 被操作了 deg[u] 次，为奇数次，点权为原点权异或上 u；其余点被操作 deg[u]-1 次，为偶数次，点权不变，达成了预期目的。
2. 若 deg[u] 为偶数，则节点 u 被操作了 deg[u] 次，为偶数次，点权不变；其余点被操作了 deg[u]-1 次，为奇数次，点权为原点权异或上 u，此时我们再以 u 本身为根节点操作一次即可达成预期目的。
考虑最大次数：
1. 若 n=1，则次数为1。
2. 若 n>1，则次数最大为 (n-1)\times2+(n-2)次。

不会超过题目要求的 3n 次。

代码

#include <bits/stdc++.h>
using namespace std;
int n,ans;
vector<int>e[200005];
void solve(){
    vector<pair<int,int>>ans;
    cin>>n;
    for(int i=1;i<=n;i++){
        e[i].clear();
    }
    for(int i=1,v,u;i<n;i++){
        cin>>v>>u;
        e[v].push_back(u);
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<e[i].size();j++){
            ans.push_back({e[i][j],i});
        }
        if(e[i].size()%2==0){
            ans.push_back({i,i});
        }
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

::::info[来自出题人队友的题目背景补充] 西安之泪是西安绵延的雨，也是一支大二队伍首次参加 XCPC 遗憾铜首的故事。