51nod 1673 树有几多愁——虚树+状压DP

多愁——虚树+状压DP"/>

51nod 1673 树有几多愁——虚树+状压DP

题目：.html#!#problemId=1673

建一个虚树。

一种贪心的想法是把较小的值填到叶子上，这样一个小值限制到的叶子比较少。

但不太会贪心了，所以考虑 DP 。只有 20 个叶子，（不是用来暴搜的！）可以状压DP了。

dp[ S ]表示选了点集 S 的叶子的方案数。再记一个 ct[ S ] 表示选这个点集的叶子、不影响到其他叶子，最多可以填几个点。

dp[ S ]可以枚举最后一个填的是哪个叶子来转移；ct[ S ]可以在第一次枚举的时候就算出来，就是看这个 “最后一个填上的叶子” 多带来几个可以填的点。

不过这样就不知道复杂度是怎样的了。反正还是过了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define db double
using namespace std;
int rdn()
{int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret;
}
ll Mx(ll a,ll b){return a>b?a:b;}
ll Mn(ll a,ll b){return a<b?a:b;}const int N=1e5+5,K=25,M=(1<<20)+5,mod=1e9+7;
int n,hd[N],xnt,to[N<<1],nxt[N<<1],dfn[N],tim;
int bin[K],lg[M],dep[N],pre[N][K],siz[N]; bool vis[N];int get_lca(int x,int y)
{if(dep[x]<dep[y])swap(x,y);int d=dep[x]-dep[y];for(int t=0;bin[t]<=d;t++)if(d&bin[t])x=pre[x][t];if(x==y)return x;for(int t=17;t>=0;t--)if(pre[x][t]!=pre[y][t])x=pre[x][t], y=pre[y][t];return pre[x][0];
}
namespace Tr{const int tN=45;int hd[N],xnt,to[tN],nxt[tN],fa[N];int sta[tN],top,p[tN],tot;int bh[N],dy[tN],vl[N],ct[M];int dp[M]; db d2[M];bool cmp(int u,int v){return dfn[u]<dfn[v];}void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;fa[y]=x;}void ini_dfs(int cr){if(vis[cr])vl[cr]=bin[bh[cr]-1];for(int i=hd[cr],v;i;i=nxt[i]){ini_dfs(v=to[i]);vl[cr]|=vl[v];}}void init(){sort(p+1,p+tot+1,cmp);sta[top=1]=p[1];for(int i=2;i<=tot;i++){int u=p[i], lca=get_lca(u,sta[top]);while(top&&dfn[lca]<dfn[sta[top]]){if(dfn[sta[top-1]]<dfn[lca])add(lca,sta[top]);else add(sta[top-1],sta[top]);top--;}if(sta[top]!=lca)sta[++top]=lca;sta[++top]=u;}for(int i=1;i<top;i++)add(sta[i],sta[i+1]);ini_dfs(sta[1]);}void solve(){init();for(int i=1,S;i<=tot;i++){S=bin[i-1]; dp[S]=1; d2[S]=1;int cr=dy[i];//dy not bhwhile(vl[fa[cr]]==S)cr=fa[cr];ct[S]=siz[cr]+(dep[cr]-dep[fa[cr]]-1);}for(int S=2;S<bin[tot];S++){if(lg[S])continue;int T=(S&-S), cr=dy[lg[T]+1], pr=cr; T=S^T;dp[S]=(ll)dp[T]*(ct[T]+1)%mod;d2[S]=d2[T]*(ct[T]+1);while(cr&&(vl[cr]|S)==S)//token!!cr=fa[cr];// if(!cr) then ct[S] is wrong but has no influencect[S]=ct[T]+dep[pr]-dep[cr];int tp=T;while(tp){T=(tp&-tp); tp^=T; T=S^T;db tmp=d2[T]*(ct[T]+1);if(tmp>d2[S])dp[S]=(ll)dp[T]*(ct[T]+1)%mod,d2[S]=d2[T]*(ct[T]+1);}}printf("%d\n",dp[bin[tot]-1]);}
}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr,int fa)
{dfn[cr]=++tim;siz[cr]=1; dep[cr]=dep[fa]+1;pre[cr][0]=fa;for(int t=1;bin[t]<=dep[cr];t++)pre[cr][t]=pre[pre[cr][t-1]][t-1];bool flag=0;for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=fa){flag=1;dfs(v,cr);siz[cr]+=siz[v];}if(!flag){vis[cr]=1; Tr::p[++Tr::tot]=cr;Tr::bh[cr]=Tr::tot;Tr::dy[Tr::tot]=cr;}
}
int main()
{n=rdn();for(int i=1,u,v;i<n;i++)u=rdn(),v=rdn(),add(u,v),add(v,u);bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1,lg[bin[i]]=i;dfs(1,0);  Tr::solve();return 0;
}

转载于:.html