HNOI 2014 米特运输（图论）

HNOI 2014 米特运输

题目大意

给一棵树，每个点有自己的权值，要求更改一些点的权值，使得整棵树满足两个条件：

• 同一个父亲的所有子节点权值相同
• 父节点的取值为所有子节点的和

答案输出最少要更改的点的数量

那么可以联想到，但凡有一个节点的权值确定了，整棵树的权值就都确定下来了

那么很容易想到通过确定一个点的权值，去dfs其他点的权值，然后判断有多少相等，然后拿n减去不用更改的，取其中的最小值就是答案

没有想到的一个点，取对数减小时间复杂度

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

inline int read(){

	int x = 0, w = 1;

	char ch = getchar();

	for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;

	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';

	return x * w;

}

const int maxn = 100010;

struct node {

    int to, nxt;

}edge[maxn << 1];

int tot, head[maxn];

inline void add(int x, int y){

    edge[++tot].to = y;

    edge[tot].nxt = head[x];

    head[x] = tot;

}

int val[maxn];

bool vis[maxn];

int w[maxn], in[maxn];

inline void dfs(int u){

    val[u] = 1;

    for(int i = head[u]; i; i = edge[i].nxt){

        if(!val[vis[i]]) w[vis[i]] = w[u] + log(in[u]), dfs(vis[i]);

    }

}

int a[maxn];

int main(){

    int n = read();

    for(int i = 1; i <= n; i++) a[i] = read();

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

        int u = read(), v = read();

        add(u, v);

        add(v, u);

        in[u]++, in[v]++;

        in[i]--;

    }

    w[1] = log(1);

    dfs(1);

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

        w[i] += log(a[i]);

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

    int cnt = 1;

    int ans = 0;

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

        if(w[i] - w[i - 1] < 1e7) cnt++;

        else ans = max(ans, cnt), cnt = 1;

    }

    cout << n - max(ans, cnt) << endl;

    return 0;

}