CF1824C 题解

· · 题解

题目大意

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

思路

首先只要让整棵树的各条根到叶子节点的异或和变成相等的，最后调节根节点 1 的值使异或和变为 0 就可以了。

所以现在考虑子树 u ，我们目标将这颗子树内的每一条从根到叶子结点的路径的异或和相等。

这里我们记录数组 b_v 为 1 到 v 的异或和，如果两个点都在 u 这颗子树内，显然 b_{v1} 就会和 b_{v2} 相等了，因为他们都将 1 到 u 上的值异或了一遍。

回归正题，每次我们显然儿子 v 的这颗子树变为都相等的值，这个时候，显然 a_v 是没有变过的，我们就可以通过调节 a_v 来使所有的路径都变成同一个值。变成的值我们就贪心地选择出现次数最多的那个值。为什么呢？因为如果你不选择次数最多的那个值，你最少会比本来的多做 1 步，这和本来的最优解的如果以后再调节祖先的值是一样的，所以这样选择肯定不劣。

然后最后在判断一下需不需要调节 a_1 就可以了。

实现方面可以用 map 记录可以修改的值的集合，可以开多个 map，每次交换两个 map 的地址更新（实际上这里也是启发式合并，每次从别的儿子节点往信息最多的信息节点合并信息，刚开始蠢笨了）。具体看代码。

代码

#include <bits/stdc++.h>//祝大家学习愉快！

using namespace std;

const int maxn=1e5+5;
int a[maxn],id[maxn],n,res=0;
struct edge{
    int to,nxt;
}e[maxn<<1];
int head[maxn],len;
map<int,int> mp[maxn],tmp;

inline void init(){
    memset(head,-1,sizeof(head));
    len=0;
}
void add(int u,int v){
    e[++len].to=v;
    e[len].nxt=head[u];
    head[u]=len;
}

void dfs(int u,int f){
    if(f&&e[head[u]].nxt==-1){
        // printf("kkkk%d\n",u);
        mp[id[u]][a[u]]++;
        return;
    }
    int maxx=1,cnt=0;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==f) continue;
        a[v]^=a[u];
        dfs(v,u);
        if(mp[id[u]].size()<mp[id[v]].size()) swap(id[u],id[v]);
        for(auto now : mp[id[v]]){
            mp[id[u]][now.first]+=now.second;
            maxx=max(maxx,mp[id[u]][now.first]);
        }
        cnt++;
    }
    res+=cnt-maxx;
    // map<int,in>
    tmp.clear();
    if(maxx>1){
        for(auto now : mp[id[u]]){
            if(now.second==maxx) tmp[now.first]=1;
        }
        swap(mp[id[u]],tmp);
    }
}

int main(){

    int n;

    init();

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        id[i]=i;
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v);
        add(v,u);
    }

    dfs(1,0);

    printf("%d\n",res+(!mp[id[1]][0]));

    return 0;
}