AtCoder Beginner Contest 163

比赛链接：Here

AB水题，

C - management

题意：给一棵 #card=math&code=N%282%5Cle%20N%5Cle2e5%29) 个节点的有根树，求每个节点的儿子数。

思路：由于输入直接给的是每个节点的父节点，直接计数即可。

const int N = 2e5 + 10;
int a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1, x; i < n; ++i)
        cin >> x, a[x] += 1;
    for (int i = 1; i <= n; ++i) cout << a[i] << "\n";
}

D - Sum of Large Numbers

题意：当前有 个整数：，求取不少于 个数的和的可能值的数量（mod 1e9+7）。

数据范围：

思路：因为 明显很大，所以取 个总和不可能等于取 个数的综合，所以只需要枚举取多少个数即可。

对于取 个数可以求出取 个值的最小最大值，在这两个值之间的值都可以取到，个数就是最大值-最小值+1。

const int mod = 1e9 + 7;
int ans = 0;
void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}
int cal(int l, int r) {
    return 1ll * (l + r) * (r - l + 1) / 2 % mod;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i = k; i <= n + 1; i += 1)
        add(ans, cal(n + 1 - i, n) - cal(0, i - 1) + 1);
    cout << ans;
}

E - Active Infants

题意：有 个小孩，第 个孩子的位置为 ，活跃值为 ，现在将 个小孩重新排列，每个小孩获得的开心值为 与重新排列前后位置差的乘积，求最大可能的开心值总和。

数据范围：

题解：可以发现将 较大的值放在边上更优，以A降序，然后就是一个区间dp，枚举当前值放左边、右边进行更新。

#card=math&code=f%5Bl%5D%5Br%5D%3D%5Cmax%20%5Cleft%28f%5Bl%2B1%5D%5Br%5D%2BA%7Bn%20o%20w%7D%20%5Ctimes%5Cleft%7Cp%7B%5Ctext%20%7Bnow%20%7D%7D-l%5Cright%7C%2C%20f%5Bl%5D%5Br-1%5D%2BA%7B%5Ctext%20%7Bnow%20%7D%7D%20%5Ctimes%5Cleft%7Cp%7B%5Ctext%20%7Bnow%20%7D%7D-r%5Cright%7C%5Cright%29)

const int N = 2e3 + 5;
ll f[N][N];
pair<int, int> p[N];
ll cal(int cnt, int l, int r) {
    if (l > r) return 0;
    if (~f[l][r]) return f[l][r];
    ll ans = 1LL * p[cnt].first * abs(p[cnt].second - l) + cal(cnt + 1, l + 1, r);
    ans = max(ans, 1LL * p[cnt].first * abs(p[cnt].second - r) + cal(cnt + 1, l, r - 1));
    return f[l][r] = ans;
}
int main() {
    int n; cin >> n;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        p[i] = {x, i};
    }
    sort(p + 1, p + n + 1, [](pair<int, int> a, pair<int, int> b) {
        return a.first > b.first;
    });
    memset(f, -1, sizeof f);
    cout << cal(1, 1, n);
    return 0;
}

F - path pass i

题意：给一棵N个节点的无根树，每个节点有一个颜色属性c，对于每个颜色，求经过这种颜色的简单路径的数量。

数据范围：

题解：把问题转换成不经过这种颜色的简单路径的数量，总数 %2F2#card=math&code=f%5BN%5D%20%3D%20N%2A%28N%2B1%29%2F2) 减去它即可。

其中不经过颜色 的简单路径的数量为：%2C%20c%7Bu%7D%3Di%7D%20f%5B%5Coperatorname%7Bdis%7D(u%2C%20v)-1%5D%7B%5Ccirc%7D#card=math&code=%5Csum%5Climits%7Bu%20%21%3Dv%2C%20u%20%21%3Dw%2C%20v%20%21%3Dw%2C%20c%7Bu%7D%3Dc%7Bv%7D%3Di%2C%20%5Cforall%20w%20%5Cin%20%5Coperatorname%7Bpath%7D%28u%2C%20v%29%2C%20c%7Bu%7D%3Di%7D%20f%5B%5Coperatorname%7Bdis%7D%28u%2C%20v%29-1%5D_%7B%5Ccirc%7D)

const int N = 2e5 + 5;
vector<int> G[N];
int C[N], num[N], sum[N];//num[i]代表i子树的节点数目，sum[i]代表以颜色为i的节点（其祖先没有颜色为i的节点）为根节点的子树大小总和
ll ans[N];
ll cal(int x) {
    return 1LL * x * (x + 1) / 2;
}
void dfs(int u, int fa) {
    int c = C[u], save = sum[c];
    num[u] = 1;
    for (auto v : G[u]) {
        if (v == fa) continue;
        int t = sum[c];
        dfs(v, u);
        int dt = sum[c] - t;
        ans[c] -= cal(num[v] - dt);//num[v]-dt代表相邻两个节点之间的节点数
        num[u] += num[v];
    }
    sum[c] = save + num[u];
}
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> C[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        ans[i] = cal(n);
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        int t = n - sum[i]; //多出来的节点还要减掉
        ans[i] -= cal(t);
        cout << ans[i] << "\n";
    }
}