team2012-F3-sol-0006

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定一个树，节点带有权值，现在可以去掉其中一个节点并将树分成多个部分，每部分的权值为其中节点的权值和，问各部分权值乘积的最大值。
解法：先dfs一遍化为有根树，并记录每个子树的权值和sum[i]，再枚举删除哪个节点x。
如果x不是是根，乘积由(sum[root]-sum[x])*sum[son1]*sum[son2]*...得到，是根将第一项去掉即可，要用高精度。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXN = 100004;
int w[MAXN], fa[MAXN], sum[MAXN];
vector<int> conn[MAXN];

struct bign
{
    int dt[1000], len;
    bign(int x = 0)
    {
        len = 1;
        dt[len] = x;
        while(dt[len] >= 10)
        {
            dt[len+1] = dt[len]/10;
            dt[len++] %= 10;
        }
    }
    void operator*=(int x)
    {
        LL cf = 0, tmp;
        for(int i=1;i<=len;i++)
        {
            tmp = dt[i];
            tmp = tmp*x + cf;
            dt[i] = tmp%10;
            cf = tmp/10;
        }
        while(cf)
        {
            dt[++len] = cf%10;
            cf /= 10;
        }
    }
    bool operator<(bign& x)
    {
        if(len < x.len) return 1;
        if(len > x.len) return 0;
        for(int i=len;i>=1;i--)
        {
            if(dt[i] < x.dt[i])  return 1;
            if(dt[i] > x.dt[i])  return 0;
        }
        return 0;
    }
    void out()
    {
        for(int i=len;i>=1;i--)
            cout<<dt[i];
        cout<<endl;
    }
};

void dfs(int x)
{
    sum[x] = w[x];
    for(int i=0;i<conn[x].size();i++)
    {
        int v = conn[x][i];
        if(v != fa[x])
        {
            fa[v] = x;
            dfs(v);
            sum[x] += sum[v];
        }
    }
}

int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>w[i];
            conn[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            int a, b;
            cin>>a>>b;
            conn[a].push_back(b);
            conn[b].push_back(a);
        }

        memset(fa, 0, sizeof(fa));
        dfs(1);
        bign ans;
        for(int i=1;i<=n;i++)
        {
            bign tmp(1);
            for(int j=0;j<conn[i].size();j++)
            {
                int v = conn[i][j];
                if(v == fa[i])
                    tmp *= sum[1]-sum[i];
                else
                    tmp *= sum[v];
            }
            if(ans < tmp)
                ans = tmp;
        }
        ans.out();
    }

    return 0;
}
}}}

题意：给定一个树，节点带有权值，现在可以去掉其中一个节点并将树分成多个部分，每部分的权值为其中节点的权值和，问各部分权值乘积的最大值。
解法：先dfs一遍化为有根树，并记录每个子树的权值和sum[i]，再枚举删除哪个节点x。
如果x不是是根，乘积由(sum[root]-sum[x])*sum[son1]*sum[son2]*...得到，是根将第一项去掉即可，要用高精度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 100004;
int w[MAXN], fa[MAXN], sum[MAXN];
vector<int> conn[MAXN];
struct bign
{
    int dt[1000], len;
    bign(int x = 0)
    {
        len = 1;
        dt[len] = x;
        while(dt[len] >= 10)
        {
            dt[len+1] = dt[len]/10;
            dt[len++] %= 10;
        }
    }
    void operator*=(int x)
    {
        LL cf = 0, tmp;
        for(int i=1;i<=len;i++)
        {
            tmp = dt[i];
            tmp = tmp*x + cf;
            dt[i] = tmp%10;
            cf = tmp/10;
        }
        while(cf)
        {
            dt[++len] = cf%10;
            cf /= 10;
        }
    }
    bool operator<(bign& x)
    {
        if(len < x.len) return 1;
        if(len > x.len) return 0;
        for(int i=len;i>=1;i--)
        {
            if(dt[i] < x.dt[i])  return 1;
            if(dt[i] > x.dt[i])  return 0;
        }
        return 0;
    }
    void out()
    {
        for(int i=len;i>=1;i--)
            cout<<dt[i];
        cout<<endl;
    }
};
void dfs(int x)
{
    sum[x] = w[x];
    for(int i=0;i<conn[x].size();i++)
    {
        int v = conn[x][i];
        if(v != fa[x])
        {
            fa[v] = x;
            dfs(v);
            sum[x] += sum[v];
        }
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>w[i];
            conn[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            int a, b;
            cin>>a>>b;
            conn[a].push_back(b);
            conn[b].push_back(a);
        }
        memset(fa, 0, sizeof(fa));
        dfs(1);
        bign ans;
        for(int i=1;i<=n;i++)
        {
            bign tmp(1);
            for(int j=0;j<conn[i].size();j++)
            {
                int v = conn[i][j];
                if(v == fa[i])
                    tmp *= sum[1]-sum[i];
                else
                    tmp *= sum[v];
            }
            if(ans < tmp)
                ans = tmp;
        }
        ans.out();
    }
    return 0;
}