裏紙

ほぼ競プロ、たまに日記

CF 701 E - Connecting Universities

問題

Problem - E - Codeforces

問題概要

頂点数nの木があり、頂点には1からnの番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、2k個の頂点番号が指定される。それらをu_1 , u_2 , \cdots , u_{2k}とする。これら2k個の頂点から、k個のペアを作る。そのペアの木における距離の総和を最大化するようにペアを作った時、その総和の値を求めよ。

  •  2 \le n \le 200000
  •  1 \le k \le n/2
  •  1 \le u_i \le n

イデア

頂点1を根として考える。すると、DFSによって次の値を各頂点に対して求めることが出来る:

  •  s_i : 頂点iを根とした部分木以下にある指定されている頂点の個数(自分も含む)

最適なペアを取ることの出来る状況を考えてみる。

そこで、頂点vとその親の間にある辺を考えてみると、その辺は min(s_v , 2k - s_v)個のペアのパス上にあることになると言える。これはなぜかというと、まず、これ以上のペアのパス上になることは、この辺を挟んだ位置にあるそれぞれの頂点の個数を考えてみると、物理的に有り得ない。逆にこれ未満である状況を考えると、vを根とする部分木の中にある頂点同士abがペアになっており、その部分木には含まれない頂点同士cdがペアになっているということになる。そして、木の性質上、このペアをacbdに変えることでaからbへのパス上の辺とcからdへのパス上の辺を全てカバーでき、かつパスを長くすることが出来る組み合わせなのでこのような組み合わせは最適ではないことが分かり、上記のことは正しいということが分かった。

ということで、結論は\sum_{i=1}^{n} min(s_i , 2k-s_i )ということになる。

そのようなマッチングを求めることもそんなに改変しなくてもできるよって書いてあるけど、パッとは思いつけない…

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int V=200000;
vector<int> G[V];

int n,k;
int u[V]={};

int s[V];
int dfs(int now, int p)
{
    if(s[now]>=0) return s[now];

    int ret=u[now];

    rep(i,G[now].size())
    {
        int nx=G[now][i];
        if(nx == p) continue;
        ret += dfs(nx,now);
    }

    return s[now]=ret;
}

int main()
{
    scanf(" %d %d", &n, &k);
    rep(i,2*k)
    {
        int a;
        scanf(" %d", &a);
        --a;
        u[a]=1;
    }
    rep(i,n-1)
    {
        int x,y;
        scanf(" %d %d", &x, &y);
        --x;
        --y;
        G[x].pb(y);
        G[y].pb(x);
    }

    memset(s,-1,sizeof(s));
    dfs(0,0);

    ll ans=0;
    rep(i,n) ans += min(s[i],2*k-s[i]);
    cout << ans << endl;
    return 0;
}