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

  1. 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 ...

  2. 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 : ...

  3. 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 ...

  4. 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 ...

  5. 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 ...

  6. [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 ...

  7. 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 ...

  8. 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 ...

  9. 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

  1. [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 ...

  2. 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 ...

  3. 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 ...

  4. 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:// ...

  5. 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 ...

  6. 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 ...

  7. 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 , ...

  8. Errors running builder &#39;DeploymentBuilder&#39; 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 ...

  9. Use tinymce Rich text

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

  10. 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 ...