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

时间：2021-10-21 23:02:21

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 v1⊕v2⊕...⊕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(1≤T≤10), denoting the number of test cases.

In each test case, the first line of the input contains two integers n(n≤1000) and m(1≤m≤210), 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(0≤vi<m), denoting the value of each node.

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

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
2
4 4
2 0 1 3
1 2
1 3
1 4
4 4
0 1 3 1
1 2
1 3
1 4
Sample Output
3 3 2 3
2 4 2 3
Source
 
 
【题意】
　　 
Byteasar有一棵nn个点的无根树，节点依次编号为11到nn，其中节点ii的权值为v_iv​i​​。

定义一棵树的价值为它所有点的权值的异或和。

现在对于每个[0,m)[0,m)的整数kk，请统计有多少TT的非空连通子树的价值等于kk。

一棵树TT的连通子树就是它的一个连通子图，并且这个图也是一棵树。

【分析】
　　先放个题解：　


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




算法1：




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




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




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




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




时间复杂度O(nmlogn)。




算法2：




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




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




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




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

代码如下：






 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define INF 0xfffffff

 #define Mod 1000000007

 #define Maxn 1100

 int v[Maxn],first[Maxn];

 struct node

 {

     int x,y,next;

 }t[*Maxn];int len;

 void ins(int x,int y)

 {

     t[++len].x=x;t[len].y=y;

     t[len].next=first[x];first[x]=len;

 }

 int mymax(int x,int y) {return x>y?x:y;}

 int sm[Maxn],mx[Maxn],ms,nm;

 int n,m;

 bool q[Maxn];

 void dfs(int x,int f,int sn)

 {

     int h=;

     mx[x]=;sm[x]=;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])

     {

         dfs(t[i].y,x,sn);

         sm[x]+=sm[t[i].y];

         mx[x]=mymax(mx[x],sm[t[i].y]);

     }

     if(sm[x]!=h) mx[x]=mymax(mx[x],sn-sm[x]);

     if(mx[x]<mx[ms]) ms=x;

 }

 int ans[Maxn],g[Maxn][Maxn];

 void get_ans(int x,int f)

 {

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])

     {

         int y=t[i].y;

         for(int j=;j<=nm;j++) g[y][j]=;

         for(int j=;j<=nm;j++) g[y][j^v[y]]=(g[y][j^v[y]]+g[x][j])%Mod;

         get_ans(y,x);

         for(int j=;j<=nm;j++) g[x][j]=(g[x][j]+g[y][j])%Mod;

     }

 }

 void ffind(int x,int f)

 {

     for(int i=;i<=nm;i++) g[x][i]=;

     g[x][v[x]]=;

     get_ans(x,f);q[x]=;

     for(int i=;i<m;i++) ans[i]=(ans[i]+g[x][i])%Mod;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])

     {

         ms=;

         dfs(t[i].y,,sm[t[i].y]);

         ffind(ms,);

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);nm=;

         memset(first,,sizeof(first));

         len=;

         for(int i=;i<=n;i++) {scanf("%d",&v[i]);nm|=v[i];}

         for(int i=;i<n;i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             ins(x,y);ins(y,x);

         }

         mx[]=INF;ms=;

         memset(q,,sizeof(q));

         dfs(,,n);

         memset(g,,sizeof(g));

         memset(ans,,sizeof(ans));

         ffind(ms,);

         for(int i=;i<m-;i++) printf("%d ",ans[i]);

         printf("%d\n",ans[m-]);

     }

     return ;

 }




[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


相关文章