Tutorial for Codeforces 1280C/1281E Jeremy Bearimy

Solution #

First let’s minimize the answer. The key observation is that at most one pair passes through the edge $(a,b)$ . This is because if two or more pair pass that edge, we can pair two vertices in the same side of that edge and get a better answer.

Furthermore, the number of pairs that pass through $(a,b)$ is $c_a\bmod 2$ , where $c_a$ the size of the component on a’s side.

For the maximized answer, the strategy is similar. The observation is that nodes of one component are paired with node of the other component. We can do the reversed thing in the minimized answer to prove this. Thus, each edge is counted $\min(c_a,c_b)$ times.

Both the maximized answer and the minimized answer can be calculated at the same time in one DFS.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}
 
vector<vector<pii>> G;
ll mx,mn;
int n;
int dfs(int u,int fa){
    int sz=1;
    for(auto [to,w]:G[u]){
        if(to==fa) continue;
        int csz=dfs(to,u);
        mx+=(ll)w*min(csz,2*n-csz);
        mn+=ll(w)*(csz%2);
        sz+=csz;
    }
    return sz;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int   tt;
    cin>>tt;
    while(tt--){
        cin>>n;
        G=vector<vector<pii>>(2*n+1);
        mx=mn=0;
        forn(i,2*n-1){
            int x,y,z;
            cin>>x>>y>>z;
            G[x].pb({y,z});
            G[y].pb({x,z});
        }
        dfs(1,0);
        cout<<mn<<' '<<mx<<endl;
    }
    return 0;
}