http://codeforces.com/problemset/problem/23/E

The question : Give a tree , Cut some edges , Make the product of all connected block sizes maximum .

Ideas :f[i][j] On behalf of the current j A contribution to i Father ( That is, it is not included in f[i][j]) What is the maximum product of , Transfer is backpack transfer

I remember the last time I counted the answers was f[i][j]*j

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iostream>

#define wk sb

#define ll long long

int tot,son[],first[],next[],go[];

int n;

struct node{

int a[],n;

}f[][];

int read(){

int t=,f=;char ch=getchar();

while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

return t*f;

}

void insert(int x,int y){

tot++;

go[tot]=y;

next[tot]=first[x];

first[x]=tot;

}

void add(int x,int y){

insert(x,y);insert(y,x);

}

node operator *(node a,node b){

node c;c.n=;for (int i=;i<=;i++) c.a[i]=;

c.n=a.n+b.n;

for (int i=;i<=a.n;i++)

for (int j=;j<=b.n;j++){

c.a[i+j-]+=a.a[i]*b.a[j];

c.a[i+j]+=c.a[i+j-]/;

c.a[i+j-]%=;

}

int j=;

while (j<=c.n||c.a[j]>){

c.a[j+]+=c.a[j]/;

c.a[j]%=;

j++;

}

while (j>&&c.a[j]==) j--;

c.n=j;

return c;

}

node make(int x){

node c;

c.n=;for (int i=;i<=;i++) c.a[i]=;

while (x){

c.a[++c.n]=x%;

x/=;

}

return c;

}

node up(node a,node b){

if (a.n>b.n) return a;

if (b.n>a.n) return b;

for (int i=a.n;i>=;i--)

if (a.a[i]>b.a[i]) return a;

else

if (b.a[i]>a.a[i]) return b;

return a;

}

void dfs(int x,int fa){

f[x][]=make();

son[x]=;

for (int i=first[x];i;i=next[i]){

int pur=go[i];

if (pur==fa) continue;

dfs(pur,x);

for (int j=son[x];j>=;j--)

for (int k=son[pur];k>=;k--)

f[x][j+k]=up(f[x][j+k],f[x][j]*f[pur][k]);

son[x]+=son[pur];

}

f[x][]=make();

for (int i=;i<=son[x];i++)

f[x][]=up(f[x][],f[x][i]*make(i));

}

int main(){

n=read();

for (int i=;i<n;i++){

int x=read(),y=read();

add(x,y);

}

dfs(,);

printf("%d",(int)f[][].a[f[][].n]);

for (int i=f[][].n-;i>=;i--)

printf("%.4d",(int)f[][].a[i]);

}

## Codeforces 23E Tree More articles about

- Codeforces 23E Tree（ Tree shape DP）
Topic link Tree $dp[x][i]$ Said to x In the subtree of the root x The size of connected fast is i When The maximum answer is use $dp[x][j]$ * $dp[y][k]$ To update $dp[x][j + k]$. ( Listen to the experts ...

- Codeforces 675D Tree Construction Splay Stretch the tree
link :https://codeforces.com/problemset/problem/675/D The question : Give a binary search tree , It's empty at first , Keep inserting numbers , After each insertion , Ask his father the weight of the node Answer key : ...

- Codeforces 570D TREE REQUESTS dfs order + Tree array Exclusive or
http://codeforces.com/problemset/problem/570/D Tree Requests time limit per test 2 seconds memory li ...

- Codeforces 570D - Tree Requests【 The tree turns linear , The prefix and 】
http://codeforces.com/contest/570/problem/D Give a tree with roots (50w A little bit )( The specified root is 1 Node is no. ), Each dot has a small letter , And then there's the most 50w A asked , Each inquiry gives x and ...

- Codeforces 1092F Tree with Maximum Cost（ Tree form DP）
Topic link :Tree with Maximum Cost The question : Given a tree , Every vertex in the tree has an attribute value ai, The edge weight of the tree is 1, seek $\sum\limits_{i = 1}^{n} dist(i, v) \cdot ...

- [Educational Round 17][Codeforces 762F. Tree nesting]
Topic linking :678F - Lena and Queries The main idea of the topic : Give two trees \(S,T\), ask \(S\) How many connected subgraphs are there with \(T\) isomorphism .\(|S|\leq 1000,|T|\leq 12\) Answer key ...

- Codeforces 911F Tree Destruction
Tree Destruction Let's take the diameter first , Then each point is combined with one end of the diameter , It's guaranteed to be optimal . #include<bits/stdc++.h> #define LL lon ...

- CodeForces 570D - Tree Requests - [DFS order + Two points ]
Topic link :https://codeforces.com/problemset/problem/570/D Answer key : This kind of question , It's basically easy to think of DFS order . then , If we save all the nodes hierarchically , Well, it's obvious that it can be rooted in ...

- Codeforces 932D - Tree
932D - Tree Ideas : On the tree anc[i][u]:u Of 2^i The ancestors mx[i][u]:u To its 2^i The maximum between ancestors , barring u pre[i][u]: With u The beginning of the incremental sequence of 2^i The ancestors sum[i ...

## Random recommendation

- [MySQL Reference Manual] 10 Globalization
10. Globalization This chapter mainly introduces globalization , Including internationalization and localization , Some of the problems : · MySQL Character sets supported in statements · How to configure different character sets for services · Select error message ...

- linq Little notes ;
1. Compare LINQ to Entities Of AsQueryable and AsEnumerable Method C# Program : Copy the contents to the clipboard program code using (testContext context = new ...

- BJOI2015 Day3
(wzj The konjac finally rolled away Cu 了 , Today's first question SB Inscription + Called 1.5h, The test also WA I got a point . Number two DP20 When I finish writing in minutes, I encounter ghosts hitting the wall , Everything is normal in the middle, and finally a negative number is output . Adjusted 1h It's found that an array is too small . And spent it again. 20+mi ...

- Let's sum up our study in the past few days django What I learned
Let's sum up our study in the past few days django What I learned http://www.tuicool.com/articles/jMVB3e Time 2014-01-12 11:40:11 CSDN Blog original text http:// ...

- 2_1 My first app hello world[wp8 Feature development and programming skills ]
2_1hello world -5min Hello everyone , I'm Xu Wenkang , In the last video we talked about , How to download the corresponding SDK. You may have spent a lot of time installing and configuring the development environment , If it's not configured yet ...

- mysql Database backup and recovery
Backup and recovery System in operation , Incremental backup and overall backup . for example : One full backup every Sunday , Monday to Saturday only back up the day . If there's something wrong with Friday's data , You can use the whole of Sunday + Monday . Tuesday . Wednesday . Come on Thursday to recover . Backup tools : Third party charges ...

- Talk show APE series ： How to be a tech savvy person
As a procedural ape , There is always a fading master . Or younger colleagues . The bull is always envious . Let's make our own miserable days BUG . The hair is soon over , People sweep two . Modify a line of code . The problem has been overcome : for example , Ten years of their own development , Underpay 10K , ...

- Errors running builder 'DeploymentBuilder' on project
Errors running builder 'DeploymentBuilder' on project 1. modify java Click save after the source code ,IDE Automatically compile and hot deploy , Note the following error : Errors o ...

- Use tinymce Rich text
1.tinymce Introduction reference https://www.tiny.cloud/docs/general-configuration-guide/basic-setup/ 2.tinymce Installation options htt ...

- python selenium Wait for the element to appear and wait for the element to disappear
In automated testing , Most of the time, there will be waiting for an element on the page to appear before the next operation , Or the list shows load , Do not proceed to the next step until the loading is completed , But the timing is uncertain , As shown in the figure below Fortunately, , stay selenium 2 And then there's a module exp ...