team2012-E1-mysol-0006

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

给出一棵树，树的权值定义为所有节点权值之和，如果砍掉一个点
则这棵树会分离成好几棵树，其价值为每棵树的权值之积
问砍哪个点，可以使得到的价值最大

算法没什么难的，先 dfs 求出每棵子树的权值之和，再枚举砍的点计算价值
关键是大整数的处理，可以拍 C++ 的大整数模板，也可以用 java

// By 猛犸也钻地 @ 2012.07.19 */
}}}

{{{
import java.io.*;
import java.util.*;
import java.math.*;

public class Summer0006 {
    static int SIZE = 100000;
    static int[] w = new int[SIZE];
    static int[] s = new int[SIZE];
    static ArrayList<Integer>[] e = new ArrayList[SIZE];
    public static void gao(int x, int src) {
        s[x] = w[x];
        for(int y : e[x]) {
            if(y == src) continue;
            gao(y, x);
            s[x] += s[y];
        }
    }
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                int n = Integer.parseInt(br.readLine()), sum = 0;
                StringTokenizer t = new StringTokenizer(br.readLine());
                for(int i = 0; i < n; i++) {
                    w[i] = Integer.parseInt(t.nextToken());
                    e[i] = new ArrayList<Integer>();
                    sum += w[i];
                }
                for(int i = 1; i < n; i++) {
                    t = new StringTokenizer(br.readLine());
                    int x = Integer.parseInt(t.nextToken()) - 1;
                    int y = Integer.parseInt(t.nextToken()) - 1;
                    e[x].add(y);
                    e[y].add(x);
                }
                gao(0, -1);
                BigInteger ans = BigInteger.ONE;
                for(int x = 0; x < n; x++) {
                    BigInteger mul = BigInteger.ONE;
                    for(int y : e[x]) {
                        if(s[y] > s[x]) {
                            mul = mul.multiply(BigInteger.valueOf(sum - s[x]));
                        } else {
                            mul = mul.multiply(BigInteger.valueOf(s[y]));
                        }
                    }
                    if(mul.compareTo(ans) > 0) {
                        ans = mul;
                    }
                }
                System.out.println(ans);
                br.readLine();
            } catch(Exception e) {
                break;
            }
        }
    }
}
}}}

/* 解题报告 //
给出一棵树，树的权值定义为所有节点权值之和，如果砍掉一个点
则这棵树会分离成好几棵树，其价值为每棵树的权值之积
问砍哪个点，可以使得到的价值最大
算法没什么难的，先 dfs 求出每棵子树的权值之和，再枚举砍的点计算价值
关键是大整数的处理，可以拍 C++ 的大整数模板，也可以用 java
// By 猛犸也钻地 @ 2012.07.19 */

import java.io.*;
import java.util.*;
import java.math.*;
public class Summer0006 {
    static int SIZE = 100000;
    static int[] w = new int[SIZE];
    static int[] s = new int[SIZE];
    static ArrayList<Integer>[] e = new ArrayList[SIZE];
    public static void gao(int x, int src) {
        s[x] = w[x];
        for(int y : e[x]) {
            if(y == src) continue;
            gao(y, x);
            s[x] += s[y];
        }
    }
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                int n = Integer.parseInt(br.readLine()), sum = 0;
                StringTokenizer t = new StringTokenizer(br.readLine());
                for(int i = 0; i < n; i++) {
                    w[i] = Integer.parseInt(t.nextToken());
                    e[i] = new ArrayList<Integer>();
                    sum += w[i];
                }
                for(int i = 1; i < n; i++) {
                    t = new StringTokenizer(br.readLine());
                    int x = Integer.parseInt(t.nextToken()) - 1;
                    int y = Integer.parseInt(t.nextToken()) - 1;
                    e[x].add(y);
                    e[y].add(x);
                }
                gao(0, -1);
                BigInteger ans = BigInteger.ONE;
                for(int x = 0; x < n; x++) {
                    BigInteger mul = BigInteger.ONE;
                    for(int y : e[x]) {
                        if(s[y] > s[x]) {
                            mul = mul.multiply(BigInteger.valueOf(sum - s[x]));
                        } else {
                            mul = mul.multiply(BigInteger.valueOf(s[y]));
                        }
                    }
                    if(mul.compareTo(ans) > 0) {
                        ans = mul;
                    }
                }
                System.out.println(ans);
                br.readLine();
            } catch(Exception e) {
                break;
            }
        }
    }
}