2012-A3-0006

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

大意：删去一颗无根树的一个顶点，使分裂的各部分的点权和的乘积最大，

比较简单的树形DP，随机选取一个作为根DFS遍历树，pt[u]表示以u为根的子数的点权和。

那么删去它的结果就是 (sum(pt[i],i =1..n) - pt[u]) * product(pt[v],v为dfs时u的子节点)

需要高精度，但是如果乘积的对数，有明显大小关系，就可以直接判断是否为答案,否则还是计算出结果比较比较保险。



{{{
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
typedef unsigned num;
typedef unsigned long long ull;
typedef long double real;

num ptr[102400],eg[204800],nx[204800],pt[102400],tot;
real ans;

struct high{
    num bit[32],L;
    static const num Dec = 1000000000u;
    void init(num x){
        memset(bit,0,sizeof(bit));
        bit[0]=x;L=1;
    }
    void operator *=(num rhs){
        ull x = 0;
        for(num i=0;i<L;++i){
            x+= bit[i]*(ull)rhs;
            bit[i] = x% Dec;
            x /= Dec;
        }
        for(;x;x/=Dec)
            bit[L++]=x%Dec;
    }
    bool operator >(const high & rhs){
        if(L != rhs.L)
            return L>rhs.L;
        else for(num j=L;j--;)
            if( bit[j]!=rhs.bit[j])
                return bit[j]>rhs.bit[j];
        return false;
    }
    void out(){
        printf("%u",bit[L-1]);
        for(num i=L-1;i--;printf("%09u",bit[i]));
    }
} tmpx,ansx;
void dfs(num u,num fr){
    real tmp = 0;
    for(num p= ptr[u],v;p;p= nx[p])
    if((v=eg[p])!=fr){
        dfs(v,u);
        pt[u]+=pt[v];
        tmp += log(pt[v]);
    }
    tmp += log(tot-pt[u]);
    if(__builtin_expect((tmp+1e-20>ans),0)){
        tmpx.init(tot -pt[u]);
        for(num p= ptr[u],v;p;p= nx[p])
        if((v=eg[p])!=fr)
            tmpx*=pt[v];
        if(tmpx>ansx)
            ansx =tmpx;
    }
}
int main(){
    srand(time(NULL));
    for(num n,rt,m;1==scanf("%u",&n);puts("")){
        for(num i=tot=0;i<n;++i){
            scanf("%u",pt+i);
            tot += pt[i];
        }
        m=0;
        memset(ptr,0,n<<2);
        for(num i=n,a,b;--i;){
            scanf("%u%u",&a,&b);
            --a;--b;
            eg[++m]=b;nx[m]=ptr[a];ptr[a]=m;
            eg[++m]=a;nx[m]=ptr[b];ptr[b]=m;
        }
        rt=rand()%n;
        ans =0;ansx.init(0);
        dfs(rt,~0);
        ansx.out();
    }
}
}}}

大意：删去一颗无根树的一个顶点，使分裂的各部分的点权和的乘积最大，

比较简单的树形DP，随机选取一个作为根DFS遍历树，pt[u]表示以u为根的子数的点权和。

那么删去它的结果就是 (sum(pt[i],i =1..n) - pt[u]) * product(pt[v],v为dfs时u的子节点)

需要高精度，但是如果乘积的对数，有明显大小关系，就可以直接判断是否为答案,否则还是计算出结果比较比较保险。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
typedef unsigned num;
typedef unsigned long long ull;
typedef long double real;
num ptr[102400],eg[204800],nx[204800],pt[102400],tot;
real ans;
struct high{
    num bit[32],L;
    static const num Dec = 1000000000u;
    void init(num x){
        memset(bit,0,sizeof(bit));
        bit[0]=x;L=1;
    }
    void operator *=(num rhs){
        ull x = 0;
        for(num i=0;i<L;++i){
            x+= bit[i]*(ull)rhs;
            bit[i] = x% Dec;
            x /= Dec;
        }
        for(;x;x/=Dec)
            bit[L++]=x%Dec;
    }
    bool operator >(const high & rhs){
        if(L != rhs.L)
            return L>rhs.L;
        else for(num j=L;j--;)
            if( bit[j]!=rhs.bit[j])
                return bit[j]>rhs.bit[j];
        return false;
    }
    void out(){
        printf("%u",bit[L-1]);
        for(num i=L-1;i--;printf("%09u",bit[i]));
    }
} tmpx,ansx;
void dfs(num u,num fr){
    real tmp = 0;
    for(num p= ptr[u],v;p;p= nx[p])
    if((v=eg[p])!=fr){
        dfs(v,u);
        pt[u]+=pt[v];
        tmp += log(pt[v]);
    }
    tmp += log(tot-pt[u]);
    if(__builtin_expect((tmp+1e-20>ans),0)){
        tmpx.init(tot -pt[u]);
        for(num p= ptr[u],v;p;p= nx[p])
        if((v=eg[p])!=fr)
            tmpx*=pt[v];
        if(tmpx>ansx)
            ansx =tmpx;
    }
}
int main(){
    srand(time(NULL));
    for(num n,rt,m;1==scanf("%u",&n);puts("")){
        for(num i=tot=0;i<n;++i){
            scanf("%u",pt+i);
            tot += pt[i];
        }
        m=0;
        memset(ptr,0,n<<2);
        for(num i=n,a,b;--i;){
            scanf("%u%u",&a,&b);
            --a;--b;
            eg[++m]=b;nx[m]=ptr[a];ptr[a]=m;
            eg[++m]=a;nx[m]=ptr[b];ptr[b]=m;
        }
        rt=rand()%n;
        ans =0;ansx.init(0);
        dfs(rt,~0);
        ansx.out();
    }
}