bzoj3162 独钓寒江雪

bzoj3162 独钓寒江雪

Input

Output

Sample Input

Sample Output

HINT

Source

2013湖北互测week1 ​​​vfk orz icefox

想做这道题很久了 看网上题解也看了很久了始终明白不了 后来有幸看到icefox巨佬的题解看到了​​学习了下scarlyw巨佬的blog 就是根据子树大小把子树的hash值都加起来即可 如果专门只求树上独立集计数的话 答案就是设dp[i][0/1]分别表示当前处于i号节点我是否选取当前节点 那么dp[i][1]=显然就是所有子树中不选的乘积

dp[i][0]就是所有子树中选与不选和的乘积

学习了一个组合数学的相关知识 当时bj集训的时候有一道题我看出来是这样做了然而不会算这个的通式 即：有n种物品要求从中选m个求问方案数 那么就是c(n+m-1)(m)

但是这题要求求本质不同的独立集个数 这时候就需要做的时候把所有本质相同的看作一个子树 那么就相当于在这些本质相同中选xx个 利用上面的组合数学相关知识即可解决由于结构不同的子树再怎么弄都不会成为本质 相同的，所以我们将结构相同的子树分成一块

#include#include#include#define g 233#define N 500010using namespace std;const int mod=1e9+7;#define ll unsigned long longinline char gc(){ static char now[1<<16],*S,*T; if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ int y,next;}data[N<<1];ll p[N],hs[N];ll dp[N][2];//1->choose this node 0->not chooseint size[N],h[N],n,G1,G2,inv[N],num; inline void get_root(int x,int fa){ size[x]=1;bool flag=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; get_root(y,x);size[x]+=size[y]; if (size[y]*2>n) flag=0; }if (size[x]*2

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。