洛谷P3237 米特运输

题目链接

题意：

　　中文题，挺好理解。就是让节点的权值等于各子节点权值之和，然后每个子节点的权值相等，原本每个点有一个权值，通过最少次的修改（可以修改成小数）使其满足要求。

分析：

　　题意一旦读明白，题什么的就简单起来了。。。首先，我们这样思考，如果我要让x节点权值不变，那么其他节点的权值都能求处来，然后判断有几个相等的就可以了，只不过是这样的话枚举节点要n次dfs，所有我们换一种思路，如果这个节点和某个节点可以“互存”（同时不改变权值），那么他们使得根的最后的值将会是一样的，反过来说，他们使得的根的值一样，那么他们可以互存也是对的（即这两句话等价），然后我们就可以直接判断不变x根节点的值将会是多少，怎么判断呢，只要判断从这里到根节点要乘多少（这个数字比较好算），然后再乘上本身的权值，只是这样下去爆long long，没有关系，换python解决问题。。。开玩笑的。。。，取个对数就好了。然后最后的答案就是n-可以“共存”的最多的节点。

　　然后就是代码

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=500000+10;
double v[maxn];
double f[maxn];
struct E{
    int to;
    int next;
    E(){
        to=next=0;
    }
}ed[maxn*2];
int head[maxn];
int tot;
void J(int a,int b){
    tot++;
    ed[tot].to=b;
    ed[tot].next=head[a];
    head[a]=tot;
}
double son[maxn];
void Dfs(int x,int fa){
    f[x]=son[fa]+f[fa];
    for(int i=head[x];i;i=ed[i].next){
        if(ed[i].to==fa)
            continue;
        son[x]+=1;
    }
    son[x]=log(son[x]);
    for(int i=head[x];i;i=ed[i].next)
        if(ed[i].to!=fa)
            Dfs(ed[i].to,x);
}
double ans[maxn];
long long ans_1[maxn];
long long ans_2[maxn];
int ans_3[maxn];
int ha[maxn];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    int js1,js2;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&js1,&js2);
        J(js1,js2);
        J(js2,js1);
    }
    Dfs(1,0);
    for(int i=1;i<=n;i++){
        v[i]=log(v[i]);
        ans[i]=f[i]+v[i];
        ans_1[i]=ans_2[i]=ans[i]*1e6;//精度的处理
    }
    sort(ans_2+1,ans_2+1+n);//离散化
    int gs=unique(ans_2+1,ans_2+1+n)-ans_2-1;
    for(int i=1;i<=n;i++)
        ans_3[i]=lower_bound(ans_2+1,ans_2+1+gs,ans_1[i])-ans_2;
    for(int i=1;i<=n;i++)
        ha[ans_3[i]]++;
    int ma=0;
    for(int i=1;i<=gs;i++)
        ma=max(ha[i],ma);
    printf("%d",n-ma);
    return 0;
}