C++14(g++5.4) 解法, 执行用时: 732ms, 内存消耗: 26076K, 提交时间: 2020-06-22 13:18:28

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int>adj[N];
int color[N], cnt[N], n, u, v, ans[N];
unordered_map<int, int>* DFS(int cur, int parent)
{
	unordered_map<int, int> *pmap = new unordered_map<int, int>, *pson = 0;
	(*pmap)[color[cur]] = cnt[cur];
	for(auto r : adj[cur])
		if(r != parent)
		{
			pson = DFS(r, cur);
			for(auto s : *pson)
				(*pmap)[s.first] += s.second;
			delete pson;
			pson = 0;
		}
	int maxcnt = 0, sum = 0;
	for(auto r : *pmap)
	{
		maxcnt = max(maxcnt, r.second);
		sum += r.second;
	}
	if(sum < maxcnt*2)
		ans[cur] = sum - maxcnt;
	else
		ans[cur] = sum / 2;

	return pmap;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
		cin >> color[i] >> cnt[i];
	DFS(1, 0);
	for(int i = 1; i <= n; i++)
		cout << ans[i] << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 736ms, 内存消耗: 83404K, 提交时间: 2020-07-04 11:46:48

#include<bits/stdc++.h>
using namespace std;
 
int a[200005],b[200005],ans[200005],sum[200005],Max[200005];
vector<int>R[200005];
map<int,int>T[200005];
void DFS(int x,int fa)
{
    int i,j;
    Max[x]=sum[x]=b[x],T[x][a[x]]+=b[x];
    for(i=0;i<R[x].size();i++)
    {
        j=R[x][i];
        if(j==fa)continue;
        DFS(j,x),sum[x]+=sum[j],Max[x]=max(Max[x],Max[j]);
        if(T[x].size()<T[j].size())swap(T[x],T[j]);
        for(auto k:T[j])T[x][k.first]+=k.second,Max[x]=max(Max[x],T[x][k.first]);
    }
    if(Max[x]*2>sum[x])ans[x]=sum[x]-Max[x];
    else ans[x]=sum[x]/2;
}
int main()
{
    int i,j,k,n;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&j,&k);
        R[j].push_back(k),R[k].push_back(j);
    }
    for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    DFS(1,0);
    for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}