首页 > 代码库 > 【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)

【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)

Tree Cutting

Problem Description
Byteasar has a tree T with n vertices conveniently labeled with 1,2,...,n. Each vertex of the tree has an integer value vi.

The value of a non-empty tree T is equal to v1v2...vn, where  denotes bitwise-xor.

Now for every integer k from [0,m), please calculate the number of non-empty subtree of T which value are equal to k.

A subtree of T is a subgraph of T that is also a tree.

 

Input
The first line of the input contains an integer T(1T10), denoting the number of test cases.

In each test case, the first line of the input contains two integers n(n1000) and m(1m210), denoting the size of the tree T and the upper-bound of v.

The second line of the input contains n integers v1,v2,v3,...,vn(0vi<m), denoting the value of each node.

Each of the following n1 lines contains two integers ai,bi, denoting an edge between vertices ai and bi(1ai,bin).

It is guaranteed that m can be represent as 2k, where k is a non-negative integer.

 

Output
For each test case, print a line with m integers, the i-th number denotes the number of non-empty subtree of T which value are equal to i.

The answer is huge, so please module 109+7.

 

Sample Input
24 42 0 1 31 21 31 44 40 1 3 11 21 31 4

 

Sample Output
3 3 2 32 4 2 3

 

Source
BestCoder Round #88
 
 
【题意】
  
Byteasar有一棵nn个点的无根树,节点依次编号为11到nn,其中节点ii的权值为v_iv?i??。定义一棵树的价值为它所有点的权值的异或和。现在对于每个[0,m)[0,m)的整数kk,请统计有多少TT的非空连通子树的价值等于kk。一棵树TT的连通子树就是它的一个连通子图,并且这个图也是一棵树。


【分析】
  先放个题解: 

本题有两种可以AC的算法。

算法1:

取一个根,将这棵树转化为有根树,并假设根必须要选,那么对于一个点来说,如果它选了,它的父亲就必须选。

求出dfs序,设f[i][j]f[i][j]表示考虑了dfs序的前ii项,目前连通块的异或和为jj的方案数。

如果ii是一个左括号,那么把ff传给儿子,并强制选择儿子;如果ii是个右括号,那么这个子树既可以选又可以不选,累加即可。

如果根必然不选,那么可以去掉这个根,变成若干棵树的子问题,这显然是点分治的形式,取重心作为根即可。

时间复杂度O(nm\log n)O(nmlogn)。

算法2:

11为根,设sum[x]sum[x]表示xx子树的异或和,假如选择的连通块的根是xx,那么要在xx子树里选择若干不相交的子树舍弃掉。

f[i][j]f[i][j]表示ii的子树里舍弃了jj的方案数,转移是个异或卷积的形式,可以用FWT加速计算。

时间复杂度O(nm\log m)O(nmlogm)。


 

   题解还是通俗易懂的,然而FWT是啥,表示不会。
  树形依赖还会一点,所以就打了第一种解法。
  然而之前没有打过点分治哦,原来重心还挺好用的....
  每次分治的时候都要找重心,那么深度就不会超过logn。。

代码如下:
技术分享
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define INF 0xfffffff10 #define Mod 100000000711 #define Maxn 110012 13 int v[Maxn],first[Maxn];14 15 struct node16 {17     int x,y,next;18 }t[2*Maxn];int len;19 20 void ins(int x,int y)21 {22     t[++len].x=x;t[len].y=y;23     t[len].next=first[x];first[x]=len;24 }25 26 int mymax(int x,int y) {return x>y?x:y;}27 28 int sm[Maxn],mx[Maxn],ms,nm;29 int n,m;30 bool q[Maxn];31 32 void dfs(int x,int f,int sn)33 {34     int h=0;35     mx[x]=0;sm[x]=1;36     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])37     {38         dfs(t[i].y,x,sn);39         sm[x]+=sm[t[i].y];40         mx[x]=mymax(mx[x],sm[t[i].y]);41     }42     if(sm[x]!=h) mx[x]=mymax(mx[x],sn-sm[x]);43     if(mx[x]<mx[ms]) ms=x;44 }45 46 int ans[Maxn],g[Maxn][Maxn];47 void get_ans(int x,int f)48 {49     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])50     {51         int y=t[i].y;52         for(int j=0;j<=nm;j++) g[y][j]=0;53         for(int j=0;j<=nm;j++) g[y][j^v[y]]=(g[y][j^v[y]]+g[x][j])%Mod;54         get_ans(y,x);55         for(int j=0;j<=nm;j++) g[x][j]=(g[x][j]+g[y][j])%Mod;56     }57 }58 59 void ffind(int x,int f)60 {61     for(int i=0;i<=nm;i++) g[x][i]=0;62     g[x][v[x]]=1;63     get_ans(x,f);q[x]=0;64     for(int i=0;i<m;i++) ans[i]=(ans[i]+g[x][i])%Mod;65     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])66     {67         ms=0;68         dfs(t[i].y,0,sm[t[i].y]);69         ffind(ms,0);70     }71 }72 73 int main()74 {75     int T;76     scanf("%d",&T);77     while(T--)78     {79         scanf("%d%d",&n,&m);nm=0;80         memset(first,0,sizeof(first));81         len=0;82         for(int i=1;i<=n;i++) {scanf("%d",&v[i]);nm|=v[i];}83         for(int i=1;i<n;i++)84         {85             int x,y;86             scanf("%d%d",&x,&y);87             ins(x,y);ins(y,x);88         }89         mx[0]=INF;ms=0;90         memset(q,1,sizeof(q));91         dfs(1,0,n);92         memset(g,0,sizeof(g));93         memset(ans,0,sizeof(ans));94         ffind(ms,0);95         for(int i=0;i<m-1;i++) printf("%d ",ans[i]);96         printf("%d\n",ans[m-1]);97     }98     return 0;99 }
[HDU 5909]

无数次傻逼加搞死自己,,233,,,

 


 

照例总结:
树形依赖型问题:
最好尽量让 泛化物品合普通物品,或者泛化物品和泛化物品的普通和(就是直接取最值的合 法)
不然 泛化物品和泛化物品的 复杂 的 合 要v^2,很慢的!!

有几种题型,如果v=n(就是说容量就是选取的点数,且选取的点数和答案相关)
可以打成n^2,计算子树答案的时候只for到字数大小即可。
这样打的话是表示子树的答案,所以不一定选原树的根的。

另一种v>>n,
如果根一定选,我们可以用dfs序dp,f[x]表示要选x这个点,并且x到根的路径的点都一定选。
中间是泛化物品合普通物品+泛化物品min|max泛化物品,总时间是nv。
那么不一定选根呢?(即选择一个联通块即可),就用点分治,算完根一定选之后,把根删掉,变成多个子树问题
每次选重心作为根可以优化到分治logn次
这一题就是这样做,总时间是nvlogn



2016-10-07 13:07:14

【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)