[HNOI2014]米特运输

时间：2022-06-08 21:25:03

显然知道一个节点就可以推出整棵树
然而直接乘会爆longlong
所以考虑取log
最后排序算众数即可

# include <stdio.h>

# include <stdlib.h>

# include <iostream>

# include <algorithm>

# include <string.h>

# include <math.h>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';

    return x * z;

}

const int MAXN(500010);

const double EPS(1e-8);

int n, cnt, ft[MAXN], a[MAXN], son[MAXN], ans;

double s[MAXN];

struct Edge{  int to, nt;  } edge[MAXN << 1];

/*

  s[i]表示i不变，根的a取对数后的值

  对s排序，取最多的众数个数num

  ans = n - num

*/

IL void Add(RG int u, RG int v){

    edge[cnt] = (Edge){v, ft[u]}; ft[u] = cnt++; son[u]++;

}

IL void Dfs(RG int u){

    for(RG int e = ft[u]; e != -1; e = edge[e].nt){

        RG int v = edge[e].to;

        s[v] = s[u] + log(son[u]);

        Dfs(v);

    }

    s[u] += log(a[u]);

}

int main(RG int argc, RG char* argv[]){

    n = Read();

    for(RG int i = 1; i <= n; i++) a[i] = Read(), ft[i] = -1;

    for(RG int i = 1, u, v; i < n; i++) u = Read(), v = Read(), Add(u, v);

    Dfs(1);

    sort(s + 1, s + n + 1);

    for(RG int i = 2, num = 1; i <= n; i++)

        if(s[i] - s[i - 1] < EPS) num++, ans = max(ans, num);

        else num = 1;

    printf("%d\n", n - ans);

    return 0;

}

相关文章