51nod 1673 树有几多愁(链表维护树形DP+状压DP)

链表维护树形DP+状压DP)"/>

51nod 1673 树有几多愁(链表维护树形DP+状压DP)

题意

lyk有一棵树，它想给这棵树重标号。
重标号后，这棵树的所有叶子节点的值为它到根的路径上的编号最小的点的编号。
这棵树的烦恼值为所有叶子节点的值的乘积。
lyk想让这棵树的烦恼值最大，你只需输出最大烦恼值对1e9+7取模后的值就可以了。
注意一开始1号节点为根，重标号后这个节点仍然为根。
数据保证叶子节点个数<=20。

思路

由于叶子节点数量很少，所以我们可以考虑状压来决定叶子节点的相对大小，如果已经确定叶子节点的相对大小了，那么就可以用贪心来解决问题了。
对于每一个祖先，它的编号一定大于它的所有儿子。
我们从大到小来枚举所有编号（这里指相对大小）。
令dp[i]表示i这个状态的节点可以得到的最大乘积。
有dp[i]可以转移到dp[i+j]，其中j这个状态仅有一个节点，并且那个节点的权值是可以算出来的。
令f[i]表示i这个状态的节点全部向根染色后最终会有多少点被染色。
通过树形DP就能求出权值了。
最大乘积可以通过对数转化为加法来判断，就可以避免高精度了。

代码

# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline char nc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int Scan(){char ch=nc();int sum=0, f=1;if (ch=='-') f=-1, ch=nc();while(!(ch>='0'&&ch<='9'))ch=nc();while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();return sum*f;
}
const int N=100005;
//Code begin....struct Node{int head, tail;}node[N];
struct Dp{LL ans; double x;}dp[(1<<20)+5];
int f[1<<20], dep[N], p, nxt[1<<20];
VI g[N];void dfs(int x, int fa){dep[x]=dep[fa]+1;int num=0;for (auto i=g[x].begin(); i!=g[x].end(); ++i) {if (*i==fa) continue;dfs(*i,x); ++num;if (num==1) node[x].head=node[*i].head, node[x].tail=node[*i].tail;else {int now=0;for (int j=node[x].head; j; j=nxt[j]) for (int k=node[*i].head; k; k=nxt[k]) {f[j^k]=f[j]+f[k]-dep[x]; nxt[now]=j^k; now=j^k;}nxt[node[x].tail]=node[*i].head; nxt[node[*i].tail]=nxt[0]; node[x].tail=now;}}if (num==0) f[1<<p]=dep[x], node[x].head=node[x].tail=1<<p, ++p;}
int main ()
{int n=Scan(), u, v;FOR(i,1,n-1) u=Scan(), v=Scan(), g[u].pb(v), g[v].pb(u);dfs(1,0);int top=1<<p;FOR(i,0,top-1) {dp[i].ans=1;FOR(j,0,p-1) if ((i>>j)&1) {if (dp[i].x<dp[i^(1<<j)].x+log(n-f[i]+1)) {dp[i].x=dp[i^(1<<j)].x+log(n-f[i]+1);dp[i].ans=dp[i^(1<<j)].ans*(n-f[i]+1)%MOD;}}}printf("%lld\n",dp[top-1].ans);return 0;
}   

转载于:.html