prow2012-A3-0006

从 Trac 迁移的文章

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

原文章内容如下：

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

比赛时写的代码。很裸的树形DP，记录每个子数的点权和就行，需要用到高精度，比赛时第一次用zju的高精度模板，结果看懂模板后发现模板里没处理爆int的情况。后来改正后AC。

第二次用这模板是AC自动机的DP，也需要高精度，有了这次经验，第二次就顺利1A了。


{{{

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
#define DIGIT   4
#define DEPTH   10000
#define MAX     100
typedef long long bignum_t[MAX+1];
void write(const bignum_t a,ostream& os=cout){
        int i,j;
            for (os<<a[i=a[0]],i--;i;i--)
                        for (j=DEPTH/10;j;j/=10)
                                        os<<a[i]/j%10;
            printf("\n");
}
int comp(const bignum_t a,const bignum_t b){
        int i;
            if (a[0]!=b[0])
                        return a[0]-b[0];
                for (i=a[0];i;i--)
                            if (a[i]!=b[i])
                                            return a[i]-b[i];
                    return 0;
}
void mul(bignum_t a,const int b){
    int i;
    if (b==0) return ;
    for (a[1]*=b,i=2;i<=a[0];i++){
        a[i]*=b;
        if (a[i-1]>=DEPTH)
            a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH;
    }
    for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}
int N,Num[110000],f[110000],father[110000];
int edge[110000],node[210000],next[210000],tot;
void insert(int a,int b){
    node[tot] = b,next[tot] = edge[a],edge[a] = tot++;
}
void dfs(int now,int fa){

    f[now] = Num[now];
    father[now] = fa;
    for (int i=edge[now];i!=-1;i=next[i])
    if (node[i]!=fa){
        dfs(node[i],now);
        f[now]+=f[node[i]];
    }
    return ;
}
bignum_t ans;

int main(){
    int i,j,a,b;
    while(scanf("%d",&N)!=EOF){
        tot = 0;
        for (i=1;i<=N;i++)
            scanf("%d",&Num[i]),edge[i] = -1;
        for (i=1;i<N;i++){
            scanf("%d%d",&a,&b);
            insert(a,b);
            insert(b,a);
        }
        if (N==1) {
            printf("0\n");
            continue;
        }
        dfs(1,0);
         ans;
        memset(ans,0,sizeof(ans));
        ans[0] = 1;
        bignum_t tmp;
        for (i=1;i<=N;i++){
                int fa = father[i];
            memset(tmp,0,sizeof(tmp));
            tmp[0] = 1;
            tmp[1] = 1;
            mul(tmp,f[1]-f[i]);
            for (j=edge[i];j!=-1;j=next[j])
                if (node[j]!=fa)
                {
                    mul(tmp,f[node[j]]);
                    //write(tmp);
                    //printf("%d %d\n",i,node[j]);
                }

            if (comp(tmp,ans)>0){
                for (j=tmp[0];j>=0;j--)
                    ans[j] = tmp[j];
            }
        }


        write(ans);



    }

}


}}}

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

比赛时写的代码。很裸的树形DP，记录每个子数的点权和就行，需要用到高精度，比赛时第一次用zju的高精度模板，结果看懂模板后发现模板里没处理爆int的情况。后来改正后AC。

第二次用这模板是AC自动机的DP，也需要高精度，有了这次经验，第二次就顺利1A了。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
#define DIGIT   4
#define DEPTH   10000
#define MAX     100
typedef long long bignum_t[MAX+1];
void write(const bignum_t a,ostream& os=cout){
        int i,j;
            for (os<<a[i=a[0]],i--;i;i--)
                        for (j=DEPTH/10;j;j/=10)
                                        os<<a[i]/j%10;
            printf("\n");
}
int comp(const bignum_t a,const bignum_t b){
        int i;
            if (a[0]!=b[0])
                        return a[0]-b[0];
                for (i=a[0];i;i--)
                            if (a[i]!=b[i])
                                            return a[i]-b[i];
                    return 0;
}
void mul(bignum_t a,const int b){
    int i;
    if (b==0) return ;
    for (a[1]*=b,i=2;i<=a[0];i++){
        a[i]*=b;
        if (a[i-1]>=DEPTH)
            a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH;
    }
    for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}
int N,Num[110000],f[110000],father[110000];
int edge[110000],node[210000],next[210000],tot;
void insert(int a,int b){
    node[tot] = b,next[tot] = edge[a],edge[a] = tot++;
}
void dfs(int now,int fa){
    f[now] = Num[now];
    father[now] = fa;
    for (int i=edge[now];i!=-1;i=next[i])
    if (node[i]!=fa){
        dfs(node[i],now);
        f[now]+=f[node[i]];
    }
    return ;
}
bignum_t ans;
int main(){
    int i,j,a,b;
    while(scanf("%d",&N)!=EOF){
        tot = 0;
        for (i=1;i<=N;i++)
            scanf("%d",&Num[i]),edge[i] = -1;
        for (i=1;i<N;i++){
            scanf("%d%d",&a,&b);
            insert(a,b);
            insert(b,a);
        }
        if (N==1) {
            printf("0\n");
            continue;
        }
        dfs(1,0);
         ans;
        memset(ans,0,sizeof(ans));
        ans[0] = 1;
        bignum_t tmp;
        for (i=1;i<=N;i++){
                int fa = father[i];
            memset(tmp,0,sizeof(tmp));
            tmp[0] = 1;
            tmp[1] = 1;
            mul(tmp,f[1]-f[i]);
            for (j=edge[i];j!=-1;j=next[j])
                if (node[j]!=fa)
                {
                    mul(tmp,f[node[j]]);
                    //write(tmp);
                    //printf("%d %d\n",i,node[j]);
                }
            if (comp(tmp,ans)>0){
                for (j=tmp[0];j>=0;j--)
                    ans[j] = tmp[j];
            }
        }
        write(ans);
    }
}