Div.2.E LuoTianyi and XOR-Tree Solution

Maverik · 2023-05-23 07:58:33 · 题解

Statement

给定一棵 n 个节点的树，根节点为 1，每个点有一个点权 a_i，每次操作可以选择一个点任意修改点权，求最少的操作次数，使得每一条根结点到叶子结点的路径上的异或和都为 0。

Solution

可以先弱化问题为让各条叶子路径异或相等的代价，再对根进行调整。直接考虑树形 dp，g_{x,i} 表示只操作 x 子树内，使经过 x 的所有叶子路径异或和变为 i 的最小操作次数。由于可以对 x 进行操作，所以 \max_i\{g_{x,i}\}-\min_i\{g_{x,i}\}\le 1。

设 f_x=\min_i\{g_{x,i}\}，S_x=\{i~|~f_x=g_{x,i}\}，y\in son_x，考虑如何转移它们：对于 \cup S_y，可以直接把一种元素上传到 S_x，其余都需要额外为1的代价，贪心的，直接取出现次数最多的上传到 S_x 即可，即：

用 set 维护集合，map 维护出现次数，启发式合并 set，复杂度 O(n\log^2 n)，代码很短。

code

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=1e5+10;
int n,a[maxn],f[maxn];
vector<int>e[maxn];
set<int>s[maxn];
inline void dfs(int x,int fa,int oplus)
{
    map<int,int>cnt;int mx=0;
    if(e[x].size()==1 && x!=1) return s[x].insert(oplus),f[x]=0,void();
    for(auto y:e[x]) if(y!=fa)
    {
        dfs(y,x,oplus^a[y]),f[x]+=(f[y]+1);
        if(s[x].size()<s[y].size()) swap(s[x],s[y]);
        for(auto v:s[y]) if(s[x].count(v)) cnt[v]++; else s[x].insert(v);
    }
    if(!cnt.empty()) 
    {
        for(auto [num,ct]:cnt) mx=max(mx,ct);
        f[x]-=(mx+1),s[x].clear();
        for(auto [num,ct]:cnt) if(ct==mx) s[x].insert(num);
    } 
    else f[x]--; 
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);
    cin>>n; for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,x,y;i<n;i++) cin>>x>>y,e[x].pb(y),e[y].pb(x);
    dfs(1,0,a[1]),cout<<f[1]+(!s[1].count(0));
    return 0;
}