洛谷P3237 米特运输

题目链接

题意：

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

分析：

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

　　然后就是代码

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn=+;

double v[maxn];

double f[maxn];

struct E{

    int to;

    int next;

    E(){

        to=next=;

    }

}ed[maxn*];

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]+=;

    }

    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=;i<=n;i++)

        scanf("%d",&v[i]);

    int js1,js2;

    for(int i=;i<=n-;i++){

        scanf("%d%d",&js1,&js2);

        J(js1,js2);

        J(js2,js1);

    }

    Dfs(,);

    for(int i=;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+,ans_2++n);//离散化

    int gs=unique(ans_2+,ans_2++n)-ans_2-;

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

        ans_3[i]=lower_bound(ans_2+,ans_2++gs,ans_1[i])-ans_2;

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

        ha[ans_3[i]]++;

    int ma=;

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

        ma=max(ha[i],ma);

    printf("%d",n-ma);

    return ;

}