首页 > 代码库 > [51nod1673]树有几多愁
[51nod1673]树有几多愁
lyk有一棵树，它想给这棵树重标号。
重标号后，这棵树的所有叶子节点的值为它到根的路径上的编号最小的点的编号。
这棵树的烦恼值为所有叶子节点的值的乘积。
lyk想让这棵树的烦恼值最大，你只需输出最大烦恼值对1e9+7取模后的值就可以了。
注意一开始1号节点为根，重标号后这个节点仍然为根。
update：数据保证叶子节点个数<=20。
Input
第一行一个数n(1<=n<=100000)。
接下来n-1行，每行两个数ai,bi(1<=ai,bi<=n)，表示存在一条边连接这两个点。
Output
一行表示答案
显然小的编号应该丢给深度大的点，也就是说，从小到大确定编号的话，一个点子树内的所有其他点都被确定了之后 这个点才会（并且一定要）被确定。
但具体叶子之间谁先谁后还是有影响的。。。
就直接状压一波，f[i]表示已经确定编号的叶子的状态为i时的最大烦恼值（叶子只要给了编号，对烦恼值的贡献就确定下来了）。
先把原树上一些没用的点删掉，只保留叶子和有多个儿子的节点（其实就是虚树...）
每次枚举一个状态的时候，直接在虚树上暴力求出到底哪些点的编号已被确定了。这样就知道下一个叶子的编号是什么...再枚举下一个确定的是哪个叶子并转移就好了。
因为答案很大，比较方案优劣的时候可以用double。。
时间复杂度O(2^n*虚树节点数)，虚树节点数大概就40个左右吧？
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 #include<cstdlib> 8 #include<bitset> 9 //#include<ctime>10 #define ll long long11 #define ull unsigned long long12 #define ui unsigned int13 #define d double14 //#define ld long double15 using namespace std;16 const int maxn=102333,modd=1000000007;const d eps=1e-7;17 struct zs{int too,pre;}e[maxn<<1],E[maxn];int tot,last[maxn],TOT,LAST[maxn];18 int sz[maxn];bool leaf[maxn],gg[maxn];19 d f[(1<<20)+23333];int g[(1<<20)+23333];20 int i,j,k,n,m;21 22 int ra;char rx;23 inline int read(){24 rx=getchar(),ra=0;25 while(rx<‘0‘)rx=getchar();26 while(rx>=‘0‘)ra=ra*10+rx-48,rx=getchar();return ra;27 }28 29 30 void dfs(int x,int fa){31 int son=0;32 for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa)33 dfs(e[i].too,x),son++,sz[x]+=sz[e[i].too];34 leaf[x]=!son,sz[x]++;35 gg[x]=!leaf[x]&&son==1;36 }37 38 inline void insert(int a,int b){39 e[++tot].too=b,e[tot].pre=last[a],last[a]=tot,40 e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;41 }42 inline void ins(int a,int b){43 E[++TOT].too=b,E[TOT].pre=LAST[a],LAST[a]=TOT;44 }45 int a[maxn],cnt;int pos[23],LEAF;int sz1[maxn],got[maxn];int num[maxn];46 void dfs2(int x,int _fa,int tmp){47 if(!gg[x]){48 a[++cnt]=x,num[cnt]=tmp;49 if(leaf[x])pos[LEAF++]=cnt;50 if(_fa)ins(_fa,cnt);51 _fa=cnt,tmp=0;52 }53 for(int i=last[x];i;i=e[i].pre)if(sz[e[i].too]<sz[x])dfs2(e[i].too,_fa,tmp+1);54 }55 int main(){56 n=read();57 for(i=1;i<n;i++)insert(read(),read());58 dfs(1,0),dfs2(1,0,1);59 60 // for(i=1;i<=cnt;i++)printf(" %d",num[i]);puts("");61 // for(i=0;i<LEAF;i++)printf(" %d",pos[i]);puts("");62 63 for(j=0;j<LEAF;j++)sz1[pos[j]]=1;64 for(j=cnt;j;j--)for(k=LAST[j];k;k=E[k].pre)sz1[j]+=sz1[E[k].too];65 66 f[0]=g[0]=1;int mx=1<<LEAF,st,tozt,tog;d tof;register int j,k;67 for(i=0;i<mx-1;i++){68 memset(got+1,0,cnt<<2);69 for(j=0;j<LEAF;j++)got[pos[j]]=(i&(1<<j))>0;70 71 for(j=cnt,st=1;j;st+=got[j]==sz1[j]?num[j]:0,j--)72 for(k=LAST[j];k;k=E[k].pre)got[j]+=got[E[k].too];73 tof=f[i]*st,tog=1ll*g[i]*st%modd;74 // printf("zt:%d st:%d\n",i,st);75 for(j=0;j<LEAF;j++)if(!(i&(1<<j))&& f[tozt=(i|(1<<j))]<tof )f[tozt]=tof,g[tozt]=tog;76 }printf("%d\n",g[mx-1]);77 }
[51nod1673]树有几多愁
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。