Codeforces 348B 思维

题意：

给出一颗以$1$为根的树，在叶子节点上长有苹果，定义子树的权值为该子树苹果数量之和，一颗平衡的树为对于树上每个点，他的每棵子树权值相同。求至少去掉多少苹果，可以使子树平衡。

方法：

如果从小子树到大子树，来平衡子树的贡献的话，是难以平衡的，譬如现在有权值为$3,4,5$的子树，要平衡他们，一个想法就是取最小值，但是对于第二颗子树，只删去一个苹果的话，如果删除的地方有兄弟节点，那么就不平衡了，难以操作。

正解思路是设$x$为最后平衡下来整棵树最大的权值和，那么因为子树权值一样，每个点的权值都要平分给他的子树们，设$tot[i]$为$i$结点的儿子数，那么根的儿子们的权值都应该是$\frac{x}{tot[1]}$，按照这个思路下去，一直到叶子结点$u$，一路平分给儿子们，必然是这样的形式$\frac{x}{tot[a]\ast tot[b]\ast ...\ast tot[z]}$，其中$a\to z$即他的所有祖先们，不妨设分母为$K$，因为一定能平分下来，那么$x$一定是$K$的倍数

，且删除数量之后，一定有$\frac{x}{K}\le v[u]$，即$x\le K\ast v[u]$，删除之后一定小于等于原来的嘛。每个叶子都有这样的等式限制，那么全部的限制就是一定是所有叶子的$K$的共同倍数，即$lcm(K_1,K_2....)$的倍数，又一定$\le min(K\ast v[1],K\ast v[2]....)$，这里的$(1,2,...)$代表所有的叶子节点，那么就能求到$x$的最大值，所以要删去的数目就是$tot-x$了，$tot$是所有点的权值总和

at all，做题的时候只从树形dp的小规模到大规模的角度思考，却忽略了平分这一点关键，一直做不出来

tips: 如果计算到某个地方的$K>tot$了，那么就需要全删掉了，为了防止爆ll，直接输出$tot$

#include
#define ll long long
using namespace std;

struct way
{
    int to,next;
}edge[200005];
int head[100005],en;

void add(int u,int v)
{
    edge[++en].to=v;
    edge[en].next=head[u];
    head[u]=en;
}

int v[200005],n;
ll ans,top=0x3f3f3f3f3f3f3f,tot[100005],totlcm=1;

void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        tot[u]++; dfs1(v,u);
    }
}

ll __lcm(ll a,ll b)
{
    return a/__gcd(a,b)*b;
}

void dfs(int u,int fa,ll k)
{
    if(k>ans)
    {
        printf("%lld\n",ans);
        exit(0);
    }
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs(v,u,k*tot[u]);
    }
    if(tot[u]==0)
    {
        totlcm=__lcm(totlcm,k);//保存到达叶子节点所有K的lcm
        top=min(top,k*v[u]);//记录上界的最小值
    }
}   

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        ans+=v[i];
    }
    for(int i=1;i<n;i++)
    {
        int u,v; scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs1(1,0); dfs(1,0,1ll); 
    cout<<ans-top/totlcm*totlcm;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72