\(\mathcal{Description}\)

Link.

给定一棵含 \(n\) 个结点的树。称点集 \(S\) 到结点 \(u\) 的会合距离为 \(\sum_{v\in S}\operatorname{dist}(u,v)\)。对于 \(|S|=1,2,\dots,n\)，求使得满足 \(S\) 一定且 \(S\) 到 \(u\) 的会合距离最小时，可能选取的 \(u\) 的个数的最大值。

\(n\le2\times10^5\)。

\(\mathcal{Solution}\)

可以发现，\(u\) 为 \(S\) 在树上的带权重心。不难得到以下结论：

当 \(2\not\mid|S|\)，答案为 \(1\)；
若存在多个合法的 \(u\)，这些 \(u\) 构成一条树链，且树链上任意一条边满足：断开这条边，两个联通块中属于 \(S\) 的结点个数相等（这也印证了上个结论）。

考虑“枚举”树链更新答案。设一条树链两端结点构成的联通块大小为 \(s_x,s_y\)，则满足 \(|S|\le2\min\{s_x,s_y\}\) 的 \(|S|\) 的答案都能用这条链的长度更新。注意到需要维护全局联通块大小这一信息，尝试钦定全局根后在有向树上做点分治。每层分治更新答案时，可以钦定当前得到的联通块的小为某条树链较小的一端，正反分别做一遍，用树状数组就能维护。

复杂度 \(\mathcal O(n\log^2n)\)。

UPD：注意到点分治取重心的性质，跨过上层分治中心的路径一定不优，所以也可以直接统计以分治中心为根的子树大小。写的时候需要注意点分的实现，分治中心必须是严格的当前树上重心。Tiw 太强力！

\(\mathcal{Code}\)

/* Clearink */

#include <cstdio>

#include <vector>

#include <algorithm>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

inline int rint() {

    int x = 0, f = 1, s = getchar();

    for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;

    for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );

    return x * f;

}

template<typename Tp>

inline void wint( Tp x ) {

    if ( x < 0 ) putchar( '-' ), x = -x;

    if ( 9 < x ) wint( x / 10 );

    putchar( x % 10 ^ '0' );

}

inline void chkmax( int& a, const int b ) { a < b && ( a = b ); }

const int MAXN = 2e5, IINF = 0x3f3f3f3f;

int n, ecnt, head[MAXN + 5], ans[MAXN + 5];

int siz[MAXN + 5], par[MAXN + 5]; // for global root.

struct Edge { int to, nxt; } graph[MAXN * 2 + 5];

bool vis[MAXN + 5];

inline void link( const int u, const int v ) {

    graph[++ecnt] = { v, head[u] }, head[u] = ecnt;

    graph[++ecnt] = { u, head[v] }, head[v] = ecnt;

}

inline void findG( const int u, const int fa, int all, int& rt ) {

    static int tsiz[MAXN + 5], wgt[MAXN + 5];

    if ( !all ) all = tsiz[u];

    tsiz[u] = 1, wgt[u] = 0;

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( !vis[v = graph[i].to] && v != fa ) {

            findG( v, u, all, rt ), tsiz[u] += tsiz[v];

            chkmax( wgt[u], tsiz[v] );

        }

    }

    chkmax( wgt[u], all - tsiz[u] );

    if ( !rt || wgt[u] < wgt[rt] ) rt = u;

}

inline void init( const int u ) {

    siz[u] = 1;

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( ( v = graph[i].to ) != par[u] ) {

            par[v] = u, init( v );

            siz[u] += siz[v];

        }

    }

}

struct BinaryIndexTree {

    int val[MAXN + 5];

    inline void upd( int x, const int v ) {

        for ( x = n - x + 1; x <= n; x += x & -x ) chkmax( val[x], v );

    }

    inline int ask( int x ) {

        int ret = -IINF;

        for ( x = n - x + 1; x; x -= x & -x ) chkmax( ret, val[x] );

        return ret;

    }

    inline void clear( int x ) {

        for ( x = n - x + 1; x <= n; x += x & -x ) val[x] = -IINF;

    }

} bit;

inline void update( const int u, const int fa, const int d, const int sr ) {

    int su = u == par[fa] ? n - siz[u] : siz[u];

    chkmax( ans[su << 1], bit.ask( su ) + d );

    chkmax( ans[( su < sr ? su : sr ) << 1], d );

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( !vis[v = graph[i].to] && v != fa ) {

            update( v, u, d + 1, sr );

        }

    }

}

inline void collect( const int u, const int fa, const int d ) {

    int su = u == par[fa] ? n - siz[u] : siz[u];

    bit.upd( su, d );

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( !vis[v = graph[i].to] && v != fa ) {

            collect( v, u, d + 1 );

        }

    }

}

inline void clear( const int u, const int fa ) {

    int su = u == par[fa] ? n - siz[u] : siz[u];

    bit.clear( su );

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( !vis[v = graph[i].to] && v != fa ) {

            clear( v, u );

        }

    }

}

inline void solve( const int u ) {

    vis[u] = true;

    static std::vector<int> son;

    son.clear();

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( !vis[v = graph[i].to] ) {

            son.push_back( v );

        }

    }

    for ( int v: son ) {

        update( v, u, 1, par[v] == u ? siz[u] - siz[v] : siz[u] );

        collect( v, u, 1 );

    }

    for ( int v: son ) clear( v, u );

    std::reverse( son.begin(), son.end() );

    for ( int v: son ) {

        update( v, u, 1, par[v] == u ? siz[u] - siz[v] : siz[u] );

        collect( v, u, 1 );

    }

    for ( int v: son ) clear( v, u );

    for ( int i = head[u], v, rt; i; i = graph[i].nxt ) {

        if ( !vis[v = graph[i].to] ) {

            findG( v, u, 0, rt = 0 );

            solve( rt );

        }

    }

}

int main() {

    n = rint();

    rep ( i, 2, n ) link( rint(), rint() );

    int rt = 0; findG( 1, 0, n, rt );

    init( rt ); // let rt be global root.

    rep ( i, 1, n ) bit.val[i] = -IINF;

    solve( rt );

    per ( i, n - 1, 1 ) chkmax( ans[i], ans[i + 1] );

    rep ( i, 1, n ) wint( i & 1 ? 1 : ans[i] + 1 ), putchar( '\n' );

    return 0;

}

巴特西

Solution -「JOISC 2021」「LOJ #3495」聚会 2

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章