Codeforces 1281E

题意：一棵$2n$个点的树让你分配$n$对居民在点上求每对居民之间路径和的最小值和最大值

思路：考虑一条边$(u, v)$

1.若要使答案尽可能大，那么这条边应该取到尽可能多次。显然，如果$u, v$的子树大小分别表示成$sz_u, sz_v$，那么这条边最多被覆盖$min(sz_u, sz_v)$次，算出每条边最多被取到的次数再乘以边长就是最大值了。

2.若要使答案尽可能小，那么我们应该让每条边最多取到$1$次，我们考虑$sz_u, sz_v$的奇偶性，发现他们是同奇偶性的。如果都是偶数，那么这条边就可以不取，因为两个子树可以内部完成，否则这条边必须取到，因为假设两个内部尽可能多的完成了，依旧会分别至少剩下$1$个点没分配，所以这条边必定被覆盖。

#include <bits/stdc++.h>

#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int n, head[N], tot, sz[N]; ll mx, mn;

struct Enode {

    int to, nxt, w;

} edge[N * 2];

void addedge(int u, int v, int w) {

    edge[tot].to = v;

    edge[tot].w = w;

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

    head[u] = tot++;

} 

void dfs(int u, int f) {

    sz[u] = 1;

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

        int v = edge[i].to, w = edge[i].w;

        if(v == f) continue;

        dfs(v, u);

        if(sz[v] & 1) mn += w;

        mx += (ll)w * min(sz[v], n - sz[v]);

        sz[u] += sz[v];

    }

}

void solve() {

    scanf("%d", &n);

    for(int i = 1; i <= 2 * n; i++) head[i] = -1, sz[i] = 0; tot = mn = mx = 0;

    n = 2 * n;

    for(int i = 1, u, v, w; i < n; i++) {

        scanf("%d%d%d", &u, &v, &w);

        addedge(u, v, w);

        addedge(v, u, w);

    }

    dfs(1, -1);

    printf("%lld %lld\n", mn, mx);

}

int main() {

    int cs; for(scanf("%d", &cs); cs--; solve());

}

巴特西

Codeforces 1281E

最新文章

热门文章