[CF348B]Apple Tree

https://www.zybuluo.com/ysner/note/1300249

题面

给一棵大小为\(n\)的树，树的每个叶子节点上有权值。

定义一颗树平衡：对于每一个结点\(u\)的子树都拥有相同的权值之和。

问至少要减掉多少权值才能使树平衡。

\(n\leq 10^5\)

解析

这题想了半天。。。

一开始的想法是\(dfs\)一遍，回溯时每个点把其所有子树减到其最小子树大小。

然而立即发现我是个**，这会影响子树内的平衡。

如果把一个点的权值定义为它子树内的权值和，

在一个子树内，所有的点都减去同一个值，才不会影响其平衡。

所以如果要在一个点减小其权值，一减就要减它所有儿子权值的\(lcm\)。

为了使当前点平衡，我们需要使其所有子树大小相等。

为了使以后的修改可行，当然要使所有子树大小都为\(lcm\)的倍数。

如果一个儿子大小小于\(lcm\)，说明不能保留子树。

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define pb(a) push_back(a)

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1e5+100;

int n,m,h[N],cnt,tag=1;

ll w[N],ans,sz[N],dp[N],s;

struct Edge{int to,nxt;}e[N<<1];

il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}

il int gi()

{

  re int x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

ll lcm(re ll a,re ll b)

{

  if(a*b>1e18+5e17) return tag=0,1;

  return a/__gcd(a,b)*b;

}

il void dfs(re int u,re int fa)

{

  dp[u]=w[u],sz[u]=1;re int Son=0;

  for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      if(v==fa) continue;

      ++Son;

      dfs(v,u);

      sz[u]=lcm(sz[u],sz[v]);

      dp[u]+=dp[v];

    }

  for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      if(v==fa) continue;

      dp[u]=min(dp[u],dp[v]-dp[v]%sz[u]);

    }

  if(!Son) Son=1;

  dp[u]*=Son;sz[u]*=Son;

}

int main()

{

  memset(h,-1,sizeof(h));

  n=gi();

  fp(i,1,n) w[i]=gi(),s+=w[i];

  fp(i,1,n-1)

    {

      re int u=gi(),v=gi();

      add(u,v);add(v,u);

    }

  dfs(1,0);

  printf("%lld\n",s-dp[1]);

  return 0;

}

巴特西

[CF348B]Apple Tree

https://www.zybuluo.com/ysner/note/1300249

题面

解析

最新文章

热门文章