现在的位置: 首页 > 综合 > 正文

codeforces 23E 树形DP

2017年04月28日 ⁄ 综合 ⁄ 共 3650字 ⁄ 字号 评论关闭

E. Tree
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Bob invented a new game with a tree (we should remind you, that a tree is a connected graph without cycles): he deletes any (possibly, zero) amount of edges of the tree, and counts the product of sizes of the connected components left after the deletion.
Your task is to find out the maximum number that Bob can get in his new game for a given tree.

Input

The first input line contains integer number n (1 ≤ n ≤ 700)
— amount of vertices in the tree. The following n - 1 lines contain the description of the edges. Each line contains the pair of vertices' indexes, joined
by an edge, aibi (1 ≤ ai, bi ≤ n).
It's guaranteed that the graph described in the input is a tree.

Output

Output the only number — the maximum product of sizes of the connected components, that Bob can get after deleting some of the tree's edges.

Sample test(s)
input
5
1 2
2 3
3 4
4 5
output
6
input
8
1 2
1 3
2 4
2 5
3 6
3 7
6 8
output
18
input
3
1 2
1 3
output
3

http://blog.csdn.net/crazy_ac/article/details/8568800

给你一棵树,让你切断一些边,使得剩下的每个连通块的点的个数的乘积最大,输出这个乘积。

n <= 700

首先,答案肯定要用高精度保存。。。。

可以贪心,也可以背包。

随便画一画可以发现剩下的连通块中,不会有某块包含长度>=3的路径,因为可以找到中间的那条边切断,使得这个路径分成两段a 和 b   (a>=2 ,b >=2), a*b>=a+b

根据这个推论 , 可以分三种情况

1:以u为根 ,且u与所有的儿子隔开

2::u与一些儿子相连,儿子们与孙子们都是断开的,不然就会有>=3的路径出现

3:u与某个儿子相连,然后这个儿子与一些孙子相连,再往下都是断开的

假设h[i]为以i为子树的答案    f[i]为 Πhj ,j是i的儿子

那么对于第一种情况,答案为f[u],第二种情况的话u需要连接上一些子树,连接某个儿子v的代价是f[u] / h[v] * f[v],所以如果只连接一个儿子,肯定就选f[v]/h[v]最大的那个儿子,因此可以先将所有的f[v]/h[v]排序,枚举一遍就好了。

第三种情况与第二种类似。。。。

如果用背包做的话状态大概是这样的dp[i][j] 表示以i为根的子树连接了j-1个儿子的最大乘积,(即i所在连通块有j个点)。转移的时候是最普通的那种转移,不过这种做法显然没有注意到上面的推论。。。

import java.util.*;  
import java.math.*;  
import java.io.*;  
  
public class Main {  
    public static void main(String[] args) {  
        InputStream inputStream = System.in;  
        OutputStream outputStream = System.out;  
        InputReader in = new InputReader(inputStream);  
        PrintWriter out = new PrintWriter(outputStream);  
        AC solver = new AC();  
        solver.solve(in, out);  
        out.close();  
    }  
}  
  
class AC {  
    class Node {  
        BigInteger h, f;  
    }  
    Comparator<Integer> cmp = new Comparator<Integer>() {  
        public int compare(Integer a,Integer b) {     
            return dp[b].f.multiply(dp[a].h).compareTo(dp[a].f.multiply(dp[b].h));  
        }  
    };  
    ArrayList<Integer> edge[] = new ArrayList[710];  
    Node dp[] = new Node[710];  
    int size[] = new int[710];  
    void dfs(int u, int f,PrintWriter out) {  
        dp[u].f = dp[u].h = BigInteger.ONE;  
        size[u] = 1;  
     // case 1 : u's component is only u  
        for(int v:edge[u]) {   
            if(v == f) continue;  
            dfs(v,u,out);  
            dp[u].f = dp[u].f.multiply(dp[v].h);  
            size[u] += size[v];  
        }  
        Collections.sort(edge[u],cmp);  
     // case 2 : u is with some of its children  
        dp[u].h = dp[u].f;  
        BigInteger cur;  
        cur = dp[u].f;  
        int son = 0;   
        for(int v:edge[u]){  
            if(v==f) continue;  
            son ++;  
            cur = cur.divide(dp[v].h).multiply(dp[v].f);  
            BigInteger tmp = cur.multiply(BigInteger.valueOf(son+1));  
            if(tmp.compareTo(dp[u].h) > 0) dp[u].h = tmp;  
        }  
     // case 3: u is with only one of its children and some children's children          
        for(int v :edge[u]) {  
            if(v==f) continue;  
            cur = dp[u].f.divide(dp[v].h).multiply(dp[v].f);  
            son = 0;  
            for(int w : edge[v]) {  
                if(w == u) continue;  
                son++;  
                cur = cur.divide(dp[w].h).multiply(dp[w].f);  
                BigInteger tmp = cur.multiply(BigInteger.valueOf(son+2));  
                if(tmp.compareTo(dp[u].h) > 0) dp[u].h = tmp;  
            }  
        }  
   
    }  
    public void solve(InputReader in, PrintWriter out) {   
        int n, a, b;  
        n = in.nextInt();  
        for (int i = 1; i <= n; i++){  
            edge[i] = new ArrayList<Integer>();  
            dp[i] = new Node();  
        }  
        for (int i = 1; i < n; i++) {  
            a = in.nextInt();  
            b = in.nextInt();  
            edge[a].add(b);  
            edge[b].add(a);  
        }  
        dfs(1,0,out);  
        out.println(dp[1].h);  
    }  
}  
  
class InputReader {  
    BufferedReader reader;  
    StringTokenizer tokenizer;  
  
    public InputReader(InputStream stream) {  
        reader = new BufferedReader(new InputStreamReader(stream));  
        tokenizer = null;  
    }  
  
    public String next() {  
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {  
            try {  
                tokenizer = new StringTokenizer(reader.readLine());  
            } catch (IOException e) {  
                throw new RuntimeException(e);  
            }  
        }  
        return tokenizer.nextToken();  
    }  
  
    public int nextInt() {  
        return Integer.parseInt(next());  
    }  
  
    public double nextDouble() {  
        return Double.parseDouble(next());  
    }  
  
    public long nextLong() {  
        return Long.parseLong(next());  
    }  
}  

抱歉!评论已关闭.