[APIO2012]派遣

标签：back   return   cto   struct   ons   [1]   clu   roo   problem   

P1552 [APIO2012]派遣

遍历每个点，维护可并堆。

遍历结束后，将所有儿子的可并堆并起来。并计算答案。

#include 
#include 
#include 
#include 
#include 

using std::vector;
using std::max;
using std::swap;

const int maxn=100010;

struct Data
{
    long long sum,val;
    int ch[2];
    int dis=0;
    int tot;
    int p,f;
    void Set(int a=0,int b=0,int c=0,int d=0,int e=0,int g=0)
    {
        sum=a;val=b;
        p=c;f=d;
        tot=e;
        dis=g;
    }
};

Data H[maxn];
vectorV[maxn];
long long I[maxn],Cost[maxn],ans;
int n,m,root;

int Find(int x)
{
    if(H[x].f==x)   return x;
    return H[x].f=Find(H[x].f);
}

int Merge(int x,int y)
{
    if(!x||!y)  return x+y;
    if(H[x].valy))    swap(x,y);
    H[x].ch[1]=Merge(H[x].ch[1],y);
    H[H[x].ch[1]].f=Find(x);
    int &Ls=H[x].ch[0],&Rs=H[x].ch[1];
    if(H[Ls].dism)
    {
        int Ls=H[pas].ch[0],Rs=H[pas].ch[1];
        H[Ls].f=Ls;H[Rs].f=Rs;
        H[pas].Set(0,0,0,Merge(Ls,Rs));
        pas=Find(pas);
    }
    ans=max(ans,I[now]*H[pas].tot);
    return ;
}

void dfs(int now)
{
    H[now].Set(Cost[now],Cost[now],now,now,1);
    for(int i=0;i

[APIO2012]派遣

标签：back   return   cto   struct   ons   [1]   clu   roo   problem   

原文地址：https://www.cnblogs.com/Lance1ot/p/10332308.html