题解 P3576 【[POI2014]MRO-Ant colony】

liuyz11 · 2020-07-10 10:23:51 · 题解

首先对于指定的那条边，可以把它拆成两棵树或者建一个0的点与这两点相连.

会想到计算每个叶子节点的每组蚂蚁到指定边后还剩多少蚂蚁，显然会超时.

我们倒过来考虑，从指定的边开始计算.

假设第 i 个节点存在数量大于等于 dp1_i 的蚂蚁，且小于等于 dp2_i的蚂蚁最终到达指定边会被吃掉(即恰好 k 只).

容易得到转移方程:

其中 c_u 表示点 u 的度

一开始 dp1_0 与 dp2_0都为k.

最后对于每一个叶子结点 i，在 m 数组中二分查找大于等于 dp1_i 且小于等于 dp2_i 的数量.

参考代码

#include <bits/stdc++.h>
#define rep(x, l, r) for(int x = l; x <= r; x++)
using namespace std;
typedef long long ll;

const ll INF = 1 << 30;
const int MAXN = 1e7 + 5;

int n, m, k, cnt, root1, root2;
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1];
int a[MAXN];
ll dp1[MAXN], dp2[MAXN], c[MAXN];

void addedge(int u, int v){
    cnt++;
    nxt[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

void add(int u, int v){
    addedge(u, v);
    addedge(v, u);
    c[u]++; c[v]++;
}

void dfs(int u, int fa){
    for(int e = head[u]; e; e = nxt[e]){
        int v = to[e];
        if(v == fa) continue;
        dp1[v] = min(INF, dp1[u] * (c[u] - 1));//防止炸longlong
        dp2[v] = min(INF, (dp2[u] + 1) * (c[u] - 1) - 1); 
        dfs(v, u);
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    rep(i, 1, m) scanf("%d", &a[i]);
    sort(a + 1, a + m + 1);
    scanf("%d%d", &root1, &root2);
    add(0, root1);//建一个0点与两个根节点连边
    add(0, root2);
    rep(i, 1, n - 2){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    dp1[0] = dp2[0] = k;
    dfs(0, -1);
    ll ans = 0;
    rep(i, 1, n)
        if(c[i] == 1){
            ans += upper_bound(a + 1, a + m + 1, dp2[i]) - lower_bound(a + 1, a + m + 1, dp1[i]);
        }
    printf("%lld\n", ans * k);//最后记得要乘上k
    return 0;
}