HDU.5909.TreeCutting(树形DPFWT/点分治)

题目链接

\(Description\)

给定一棵树&＃xff0c;每个点有权值&＃xff0c;在\([0,m-1]\)之间。求异或和为\(0,1,...,m-1\)的非空连通块各有多少个。
\(n\leq 1000,m\leq 2^{10}\)。

\(Solution\)

在每个连通块的根节点处统计。\(f[x][k]\)表示以\(x\)为根&＃xff0c;异或和为\(k\)的连通块&＃xff08;子树&＃xff09;有多少个。
那么\(f[x][k]&＃61;f[x][k]&＃43;\sum_{i\ \mathbb{xor}\ j&＃61;k}f[x][i]*f[v][j],\ v&＃61;son[x]\)。
后一部分就是异或卷积&＃xff0c;可以用\(FWT\)优化。

具体实现&＃xff0c;不需要每次转移一棵子树都\(FWT,IFWT\)一次。中间过程一直用\(FWT\)后的\(f\)计算就可以了。
可能有的问题是&＃xff0c;\(f\)本身&＃xff08;\(f[x][k]\)&＃xff09;还要加上自己&＃xff0c;必须在转移的时候\(IFWT\)回去&＃xff1f;不妨在\(f[v]\)计算完之后\(IFWT(f[v])\)&＃xff0c;令\(f[v][0]&＃43;&＃43;\)&＃xff0c;然后再\(FWT\)回去&＃xff0c;用这个\(f[v]\)去更新\(f[x]\)。这样就可以直接用\(FWT\)后的\(f\)计算了。
\(f[x][0]\)在计算前是不能\(&＃43;1\)的&＃xff0c;因为必须要求\(f[x]\)代表的非空连通块是以\(x\)为根的。
最后把所有\(f[i]\ IFWT\)回去&＃xff0c;再令\(f[i][0]\)--。
复杂度\(O(nm\log m)\)。

所以有这两种写法的差异。。
https://www.cnblogs.com/cjyyb/p/9065611.html
https://blog.csdn.net/clover_hxy/article/details/72722352
还可以点分治。。在第二篇里有。不想写了。

//858MS 5528K(怎么那么多跑的很快的啊--点分&＃xff1f;)
#include
#include
#include
#include
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS&＃61;&＃61;TT&&(TT&＃61;(SS&＃61;IN)&＃43;fread(IN,1,MAXIN,stdin),SS&＃61;&＃61;TT)?EOF:*SS&＃43;&＃43;)
#define inv2 500000004
#define mod 1000000007
#define Add(x,y) (x&＃43;y>&＃61;mod?x&＃43;y-mod:x&＃43;y)
#define Sub(x,y) (xtypedef long long LL;
const int N&＃61;1024&＃43;5;int lim,Enum,H[N],nxt[N<<1],to[N<<1],f[1005][N];
char IN[MAXIN],*SS&＃61;IN,*TT&＃61;IN;inline int read()
{int now&＃61;0;register char c&＃61;gc();for(;!isdigit(c);c&＃61;gc());for(;isdigit(c);now&＃61;now*10&＃43;c-&＃39;0&＃39;,c&＃61;gc());return now;
}
inline void AE(int u,int v)
{to[&＃43;&＃43;Enum]&＃61;v, nxt[Enum]&＃61;H[u], H[u]&＃61;Enum;to[&＃43;&＃43;Enum]&＃61;u, nxt[Enum]&＃61;H[v], H[v]&＃61;Enum;
}
void FWT(int *a,int lim,int opt)
{for(int i&＃61;2; i<&＃61;lim; i<<&＃61;1)for(int j&＃61;0,mid&＃61;i>>1; j}
void DFS(int x,int fa)
{FWT(f[x],lim,1);for(int i&＃61;H[x],v; i; i&＃61;nxt[i])if((v&＃61;to[i])!&＃61;fa){DFS(v,x);for(int j&＃61;0; j}int main()
{static LL Ans[N];for(int T&＃61;read(); T--; ){Enum&＃61;0, memset(H,0,sizeof H);memset(f,0,sizeof f), memset(Ans,0,sizeof Ans);int n&＃61;read(),m&＃61;read(); lim&＃61;m;for(int i&＃61;1; i<&＃61;n; &＃43;&＃43;i) &＃43;&＃43;f[i][read()];for(int i&＃61;1; i}