Chlience

【题解】LOJ 2207 「HNOI2014」米特运输
Problem给定一个树形结构,每个点有权值 $a$问最少需要修改多少个点权,使得每个点的子节点点权相等,且该点点...
扫描右侧二维码阅读全文
11
2019/02

【题解】LOJ 2207 「HNOI2014」米特运输

Problem

给定一个树形结构,每个点有权值 $a$

问最少需要修改多少个点权,使得每个点的子节点点权相等,且该点点权等于其点权和

Thought

发现对于任意一个点,只要确定其权值,所有点的权值即可确定

那么考虑确定每个点后根节点的权值,根节点权值恰好是到该点路径上所有点的子节点数量乘积乘上该点权值

那么直接算出相同的权值最多有多少个即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 500010;
const int mod = 1000000007;
int n;
int a[N];
int fa[N], son[N];
struct Edge {
    int t, n;
}e[N];
int head[N], tot;
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
map <int, int> Map;
int ans = 0;
void dfs(int x, int tim) {
    Map[1ll * tim * a[x] % mod] ++;
    ans = max(ans, Map[1ll * tim * a[x] % mod]);
    tim = 1ll * tim * son[x] % mod;
    for(int i = head[x]; i; i = e[i].n)
        dfs(e[i].t, tim);
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    for(int i = 1; i < n; ++ i) {
        int a = read(), b = read();
        addedge(a, b);
        ++ son[a];
        fa[b] = a;
    }
    for(int i = 1; i <= n; ++ i)
        if(fa[i] == 0) {
            dfs(i, 1);
            break;
        }
    printf("%d\n", n - ans);
    return 0;
}
Last modification:February 11th, 2019 at 09:49 pm

Leave a Comment