洛谷3237 [HNOI2014]米特运输

Luogu

BZOJ

分析

简化版题意

给一棵树,每个点有一个权值,要求修改一些点的权值,使得:

  • 同一个父亲的儿子权值必须相同
  • 父亲的权值必须是所有儿子权值之和

问最少需要修改多少个点。


发现对于整棵树,只要有一个点的权值确定了,整棵树的权值也就确定了。

例如下图(copy的):

设$f[i]=(\prod\limits_{v}son[v])\cdot a[i]$,其中$v$是$1$到$i$的父节点的路径上的点,$son[v]$是$v$的子节点个数,$a[i]$是$i$的权值。

然后,如果$f[i]=f[j]$,则$i$和$j$在同一种合法方案中。正确性显然。

所以求出$f$后找出众数的数量$cnt$,然后答案就是$n-cnt$。

注意会爆long long,需要用$\log$改乘为加($log_c(ab)=log_c(a)+log_c(b)$)。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;
const double eps=1e-8;

struct Edge { int v,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n;
int a[N],deg[N];
double f[N];

inline void dfs(int u,int fa,double s) {
    f[u]=s+log(a[u]);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u,s+log(deg[u]));
    }
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),++deg[u];
    }
    dfs(1,0,log(1)); sort(f+1,f+n+1);
    int ans=0;
    for (re int i=2,cnt=1;i<=n;++i) {
        if (f[i]-f[i-1]<=eps) ans=max(ans,++cnt);
        else cnt=1;
    }
    printf("%d\n",n-ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 26 PM

发表评论