月出皎兮,佼人僚兮。
题意
给一棵树,每个点有两个属性a,b 代表这个点有b个a颜色。
颜色不一样的点可以匹配(不管有没有连)。
1是根节点。
让求每颗子树的最大匹配。
题解。
性质:在一堆颜色中找个个数的最大值,
如果最大值小于等于所有颜色的个数的和,那么所有的都可以匹配即sum/2。
如果最大值大于所有颜色个数的和,那么匹配的数量是sum - maxx。
这个我怎么不知道? 我咋想不到。。一直在纠结怎么快速得到匹配的数量,就是想不出来 最近太差劲了。菜
知道这个性质就好做了,因为是统计子树的问题,很容易想到dsu on tree。
所以代码:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
a %= mod;ll ans = 1;while(b){
if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
bool operator()(const pii & a, const pii & b){
return a.second > b.second;}};
int lb(int x){
return x & -x;}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 2e5+5;
std::vector<int> vv[maxn];
int num[maxn];
int son[maxn];
int ans[maxn];
int a[maxn];
int b[maxn];
int eson;
ll cnt[maxn];
ll maxx = 0;
ll sum[maxn];
void solve(int x,int fa)
{
cnt[a[x]] += b[x];
maxx = max(maxx,cnt[a[x]]);
for(int i = 0; i < vv[x].size(); i ++ )
{
int v = vv[x][i];
if(v == fa || v == eson)
continue;
solve(v,x);
}
}
void del(int x,int fa)
{
cnt[a[x]] -= b[x];
for (int i = 0; i < vv[x].size(); i ++ )
{
int v= vv[x][i];
if(v == fa)
continue;
del(v,x);
}
}
void dsu(int x,int fa,int f)
{
for (int i = 0; i < vv[x].size(); i ++ )
{
int v = vv[x][i];
if(v == fa || v == son[x])
continue;
dsu(v,x,1);
}
if(son[x])
dsu(son[x],x,0);
eson = son[x];
solve(x,fa);
eson = 0;
// printf("%d %lld %lld\n",x,sum[x],maxx);
if(maxx <= sum[x] / 2)
{
ans[x] = sum[x] / 2;
}
else
ans[x] = sum[x] - maxx;
if(f)
{
del(x,fa);
maxx = 0;
}
}
void dfs(int x,int fa)
{
son[x] = 0;
sum[x] = b[x];
num[x] = 1;
for (int i = 0; i < vv[x].size(); i ++ )
{
int v = vv[x][i];
if(v == fa)
continue;
dfs(v,x);
num[x] += num[v];
sum[x] += sum[v];
if(num[v] > num[son[x]])
son[x] = v;
}
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 1; i < n; i ++ )
{
int x,y;
scanf("%d%d",&x,&y);
vv[x].pb(y);
vv[y].pb(x);
}
for (int i= 1; i <= n; i ++ )
scanf("%d%d",&a[i],&b[i]);
dfs(1,0);
dsu(1,0,0);
for (int i = 1; i <= n; i ++ )
printf("%d\n", ans[i]);
}