dfs

dfs遍历树对于每个节点，开一个数组记录子树内节点。对于每个子树进行遍历用map统计，除去最多的颜色节点，然后进行异或，取每个子树异或的最大值。 $\\$ 整体时间复杂度o(n^2logn)

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 10005
vector<int>g[N];
vector<int>a[N];
int col[N];
int n;
int dfs(int u,int fa){
	int ans=0;
	a[u].push_back(u);
	for(int v:g[u]){
		if(v==fa) continue;
		ans=max(dfs(v,u),ans);
		for(int w:a[v]){
			a[u].push_back(w);
		}
	}
	map<int,int>mp;
	int mx=0;
	for(int v:a[u]){
		mp[col[v]]+=1;
		mx=max(mx,mp[col[v]]);
	}
	int res=0;
	for(auto[i,j]:mp){
		if(j!=mx&&j%2==1) res^=i;
	}
	return max(res,ans);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>col[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout<<dfs(1,0)<<'\n';
	return 0;
}

题目内容

小红的朋友送了他一棵节点数为 $n$ 的糖果树($1$号点为根节点)，树上的每个糖果都有一个颜色。

小红吃糖果有一个习惯，他每次都会吃掉一整个子树的糖果，他喜欢与众不同，所以每次吃之前他都会把出现次数最多的颜色的糖果扔掉(可能有多个出现次数最多的颜色，此时要全部扔掉)，他可以选择任意一棵子树吃掉，但他只能吃一次，因此他想知道他一次能吃到的所有糖果的颜色的异或和最大是多少(如果吃到了多个颜色相同的糖果，也需要做多次异或)，你能帮帮他吗?

输入描述

第一行一个整数$n(1 ≤ n ≤ 1000)$。表示树的节点数量。

第二行$n$个整数$a_i(1 ≤a_i ≤ n)$，表示节点$i$的颜色。

接下来$n-1$行，每行两个整数$u,v$表示节点$u$和节点$v$之间有一条边。

输出描述

输出仅有一行，一个整数表示他一次能吃到的糖果的颜色的异或和最大值。

样例1

输入

4
1 2 3 4
1 2
2 3
2 4

输出

0

说明

四个节点颜色各不相同。吃掉任意子树都会在吃之前把所有糖果扔掉，因此结果为$0$。

样例2

输入

4
1 1 2 2
1 2
2 3
2 4

输出

1

说明

吃掉以节点$3$或节点$4$为根的子树都只有一个节点，结果都为$0$，以$1$为根节点时颜色为$1$和颜色为$2$的节点数量都为$2$，因此结果也为$0$。

吃掉以$2$为根的子树时节点$3$和节点$4$颜色都为$2$被删除，结果为节点$2$的颜色$1$。