hdu 5909 Tree Cutting —— 点分治

时间：2021-07-05 22:59:14

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5909

点分治，每次的 rt 是必选的点；

考虑必须选根的一个连通块，可以DP，决策就是在每个子树中决定选不选子树根，如果不选就跳过这个子树；

于是可以转化成 dfs 序上的DP；

每次重新标记一遍 dfs 序，但不改动 siz (也许可以改动但T了?)，可能因为 siz 还和点分治的过程有关。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const xn=,inf=,mod=1e9+;

int n,m,v[xn],hd[xn],ct,to[xn<<],nxt[xn<<],siz[xn],dfn[xn],g[xn],tim;

int ans[xn],f[xn][xn],rt,mx,nt[xn];

bool vis[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void upt(int &x,int y){x+=y; while(x>=mod)x-=mod; while(x<)x+=mod;}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void getrt(int x,int fa,int sum)

{

  int nmx=; siz[x]=;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa||vis[u])continue;

      getrt(u,x,sum); siz[x]+=siz[u];

      if(siz[u]>nmx)nmx=siz[u];

    }

  nmx=max(nmx,sum-siz[x]);

  if(nmx<mx)mx=nmx,rt=x;

}

void dfs(int x,int fa)

{

  dfn[x]=++tim; g[tim]=v[x];

  for(int i=hd[x],u;i;i=nxt[i])

    if((u=to[i])!=fa&&!vis[u])dfs(u,x);

  nt[dfn[x]]=tim+;

}

void work(int x,int ss)

{

  vis[x]=; tim=; dfs(x,);

  for(int i=;i<=ss+;i++)memset(f[i],,sizeof f[i]);

  f[][g[]]=;

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

    for(int j=;j<m;j++)

      if(f[i][j])upt(f[i+][j^g[i]],f[i][j]),upt(f[nt[i]][j],f[i][j]);

  //printf("x=%d ss=%d\n",x,ss);

  for(int j=;j<m;j++)upt(ans[j],f[ss+][j]);

  //,printf("f[%d][%d]=%d\n",dfn[x]+siz[x],j,f[dfn[x]+siz[x]][j]);

  for(int i=hd[x],u;i;i=nxt[i])

    if(!vis[u=to[i]])

      {

    int ns=(siz[u]>siz[x]?ss-siz[x]:siz[u]);

    mx=inf; getrt(u,,ns); work(rt,ns);

      }

}

int main()

{

  int T=rd();

  while(T--)

    {

      n=rd(); m=rd();

      for(int i=;i<=n;i++)v[i]=rd();

      ct=; tim=;

      for(int i=;i<=n;i++)hd[i]=;

      for(int i=,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x);

      for(int j=;j<m;j++)ans[j]=;

      for(int i=;i<=n;i++)vis[i]=;

      mx=inf; getrt(,,n); work(rt,n);

      for(int j=;j<m;j++)printf("%d%c",ans[j],j==m-?'\n':' ');

    }

  return ;

}

相关文章