bzoj 2809:[Appio 2012]dispatching

リンク:http://www.lydsy.com/JudgeOnline/problem.php?id=2809
中国語の問題です.
分析:葉から根への貪欲さが一番少ないということを知っている人は、頭数と根のリーダーシップを計算すれば、葉から根への統合は総予算を超えて給料の高い忍者を削除できるということです.
コード:

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=100010;
const int MAX=151;
const int MOD=1000000007;
const int MOD1=100000007;
const int MOD2=100000009;
const int INF=2100000000;
const double EPS=0.00000001;
typedef long long ll;
typedef unsigned long long uI64;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans=0;
int m,c[N],l[N];
int tot,d[N],h[N],pre[N];
int lc[N],rc[N],fa[N],sum[N],peo[N];
void add(int a,int b) {
    d[tot]=b;pre[tot]=h[a];h[a]=tot++;
}
int find_fa(int x) {
    if (fa[x]==x) return x;
    return fa[x]=find_fa(fa[x]);
}
int mergee(int a,int b) {
    if (!a||!b) return a+b;
    if (c[a]<c[b]) { a^=b;b^=a;a^=b; }
    rc[a]=mergee(rc[a],b);
    if (h[lc[a]]<h[rc[a]]) { lc[a]^=rc[a];rc[a]^=lc[a];lc[a]^=rc[a]; }
    h[a]=h[rc[a]]+1;
    return a;
}
void dfs(int x) {
    int i,a,b,f;
    for (i=h[x];i!=-1;i=pre[i]) {
        dfs(d[i]);
        a=find_fa(x);
        b=find_fa(d[i]);
        f=mergee(a,b);
        fa[a]=fa[b]=fa[f]=f;
        sum[f]=sum[a]+sum[b];peo[f]=peo[a]+peo[b];
        while (sum[f]>m) {
            fa[lc[f]]=fa[rc[f]]=mergee(lc[f],rc[f]);
            fa[f]=fa[lc[f]];
            sum[fa[f]]=sum[f]-c[f];peo[fa[f]]=peo[f]-1;
            f=fa[f];
        }
    }
    f=find_fa(x);
    ans=max(ans,(ll)peo[f]*l[x]);
}
int main()
{
    int i,n,x;
    scanf("%d%d", &n, &m);
    tot=0;
    memset(h,-1,sizeof(h));
    for (i=1;i<=n;i++) {
        scanf("%d%d%d", &x, &c[i], &l[i]);
        add(x,i);
    }
    lc[0]=rc[0]=fa[0]=sum[0]=peo[0]=0;
    for (i=1;i<=n;i++) {
        lc[i]=rc[i]=0;fa[i]=i;sum[i]=c[i];peo[i]=1;
    }
    dfs(1);
    printf("%lld
", ans);
    return 0;
}


/*
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

7 6
0 3 4
1 3 7
2 2 5
2 2 5
1 5 4
5 3 1
5 2 5

*/