problem

洛谷鏈接

solution

這種要求值和恰好為 $k$ 的題目，一般要先明確值和的取值范圍。

所以我們先來確定一下值和的最小值和最大值。

將一條路徑拆成若干條邊，單獨計算每條邊對路徑的貢獻。

假設一條邊將樹劃分成 $S,T$ 集合。因為 $n$ 為偶數，所以 $S,T$ 同奇偶。

則貢獻最大值就是每條路徑都經過該邊，最小值就是盡量內部消化。

每個點只能匹配一個點，故最大值為 $\min (|S|,|T|)$，最小值為 $|S|\&1$。

這個 $\min$ 我們想辦法去掉，$|S|+|T|=n?\min (|S|,|T|)\le \frac{n}{2}$。

啊——重心。其定義就是任意一個親兒子子樹的大小都滿足 $siz[x]\le n?siz[x]$。

即值和最大值就是盡量所有路徑都過重心，$i?i+\frac{n}{2}$ $\text{dfn}$ 序配對。

不妨從最大值考慮下放成 $k$。

如圖，假設原先是 $1?v,2?u?1?2,u?v$，這樣子就做到了對答案減少 $2?dep[lca(u,v)]$ 的效果。

還發現，每次貢獻的改變都是偶數，所以如果 $k$ 與最大值不同奇偶也是無解的。

像倍增一樣的，從大往小放縮。

找到一個深度最深的且子樹大小（含自己）至少為 $2$ 的點。

先考慮讓這個點的子樹內產生一對內部匹配，那么減少的貢獻就是最大的。

• 如果減少這個貢獻，還沒有下放到 $k$，就繼續上面的操作。
• 如果下放過了，因為路徑肯定是連續的，那么從重心到這個點深度層中一定恰好有一個點能恰好使得最后下放到 $k$。

具體而言，構造如下：

• $k=Max$，直接 $\text{dfn}$ 序后，$i?i+\frac{n}{2}$。

• $k<Max$。假設重心為 $root$。

  取 $root$ 親兒子中子樹大小最大的點 $x$，則 $siz[x]\ge 2$。

  取 $x$ 后代中最深的且子樹大小至少為 $2$ 的點 $y$。

  • $2dep[y]<Max?k$，可以選擇兩個 $lca=y$ 的點內部匹配并刪除，$Max$ 和 $k$ 的差距縮小 $2dep[y]$，回到上一步。

  • $2dep[y]\ge Max?k$，這一條路徑上一定有一個點 $z,dep[z]=\frac{Max?k}{2}$，同樣選擇兩個 $lca=z$ 的點內部匹配。break 整個過程。

    用 set 存子樹內的深度及點編號，到時候一個 lower_bound 查即可。

  當然這個點可以是 $y,z$ 本身。

過程中的匹配變化，$k<Max,2dep[y]\le Max?k$，不會讓重心移動，所以不用每次都重新求，set 模擬維護。

具體而言，算法流程如下：

• dfs1 獲得重心以及值和的上下界。迅速特判 $k$ 能夠被構造出來。

• 對重心的每個親兒子分別進行子樹 dfs2，s[] 記錄子樹內每個點的深度，子樹大小，未配對兒子個數，隸屬于重心的親兒子的編號。深度為第一關鍵字。

  只有這個親兒子子樹大小 $\ge 2$ 的時候，才能用于后面的匹配下放，才放入候選方案 g 中。子樹大小為第一關鍵字。

• 從最大親兒子 $x$ 開始考慮，用 lower_bound 找構造中的 $y$，并進行判斷。

  進行信息修正。$x$ 子樹中能匹配的個數減少 $2,siz[x]?=2$。隨便找兩個 $y$ 內未匹配的點配對輸出，打上已配對標記。

  重復本條流程直到跳出。

• 剩下的未匹配點就是普通的 $i?i+\frac{n}{2}$ 配對，dfs3 找所有未匹配點（這些點可能已經被一些匹配點割裂成不聯通的幾個部分了）。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 set < pair < int, int > > s[maxn], g; vector < int > G[maxn], id; int n, k; int center = 1e18, root, Min, Max; bool vis[maxn]; int f[maxn], son_cnt[maxn], siz[maxn], dep[maxn], belong[maxn];void dfs1( int u, int fa ) {int maxson = 0; siz[u] = 1;for( int v : G[u] ) {if( v == fa ) continue;dfs1( v, u );siz[u] += siz[v];maxson = max( maxson, siz[v] );}maxson = max( maxson, n - siz[u] );if( maxson < center ) center = maxson, root = u;if( u ^ 1 ) Min += siz[u] & 1, Max += min( siz[u], n - siz[u] ); }void dfs2( int u, int fa, int t ) {belong[u] = t, dep[u] = dep[fa] + 1, siz[u] = 1, f[u] = fa;for( int v : G[u] ) {if( v == fa ) continue;else dfs2( v, u, t );son_cnt[u] ++, siz[u] += siz[v];}if( son_cnt[u] ) s[t].insert( make_pair( dep[u], u ) ); }void dfs3( int u, int fa ) {if( ! vis[u] ) id.push_back( u );for( int v : G[u] ) if( v ^ fa ) dfs3( v, u ); }void _delete( int x ) {vis[x] = 1;son_cnt[f[x]] --;if( ! son_cnt[f[x]] ) s[belong[f[x]]].erase( make_pair( dep[f[x]], f[x] ) ); }void match( int x ) {vector < int > use;for( int i : G[x] ) if( i ^ f[x] and ! vis[i] ) use.push_back( i );if( ! vis[x] ) use.push_back( x );printf( "%lld %lld\n", use[0], use[1] );_delete( use[0] ), _delete( use[1] ); }signed main() {scanf( "%lld %lld", &n, &k );for( int i = 1, u, v;i < n;i ++ ) {scanf( "%lld %lld", &u, &v );G[u].push_back( v );G[v].push_back( u );}dfs1( 1, 0 );if( k < Min or Max < k or ( Max - k ) & 1 ) return ! printf( "NO\n" );else printf( "YES\n" );for( int x : G[root] ) {dfs2( x, root, x );if( siz[x] > 1 ) g.insert( make_pair( siz[x], x ) );}int rest = Max - k;while( rest ) {int x = g.rbegin() -> second;g.erase( make_pair( siz[x], x ) );int y = s[x].rbegin() -> second;if( ( dep[y] << 1 ) >= rest ) {y = s[x].lower_bound( make_pair( rest >> 1, 0 ) ) -> second;match( y );break;}else {rest -= ( dep[y] << 1 );siz[x] -= 2;match( y );if( siz[x] > 1 ) g.insert( make_pair( siz[x], x ) );}}dfs3( root, 0 );for( int i = 0;i < ( id.size() >> 1 );i ++ )printf( "%lld %lld\n", id[i], id[i + ( id.size() >> 1 )] );return 0; }

總結

以上是生活随笔為你收集整理的CodeForces 1396E Distance Matching（构造+树的重心+dfs+set）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。