CF2134D 题解

脑电波题，但是很像某道 zr 模拟赛题，于是场切了（

Solution

我们首先进行一些观察，可以发现一些性质。

• 一次操作使任意两点间距离最多增加 $1$，树的直径长度最多增加 $1$。
• 设当前直径为 $D$，最终得到的链的直径是 $n - 1$，所以操作数 $\geq (n - 1) - D$。

最优的第一步显然可以就让直径 $+1$。

构造这一步，我们注意到可以在直径上取一个度数 $\geq 3$ 的点 $b$，$a$ 取其父亲，$c$ 取 $b$ 的邻居中任意一个不在直径上的节点即可。

考虑正确性，为什么这一步能让直径增加 $1$？

• 本来直径的形态是 $\cdots-a-b-t-\cdots$。
• 操作 $(a, b, c)$ 会把 $t$ 挂到 $c$ 下面，于是就变成了 $\cdots-a-b-c-t-\cdots$，直径长度增加 $1$。

实现上，可以用 bfs 或 dfs 求出树的直径，然后枚举直径上的点找就可以了。

Code

::::info[在这]

// Problem: D. Sliding Tree
// Contest: Codeforces - Codeforces Round 1045 (Div. 2)
// URL: https://codeforces.com/contest/2134/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

const int maxn = 2e5 + 5 ;

int n ;
vector<int> g[maxn] ;
int deg[maxn] ;

int dis[maxn], fa[maxn] ;
int bfs(int s) {
    rep(i, 1, n) {
        dis[i] = fa[i] = -1 ;
    }
    queue<int> q ;
    q.push(s) ; dis[s] = 0 ;
    while(!q.empty()) {
        int u = q.front() ; q.pop() ;
        for(auto v : g[u]) {
            if(dis[v] == -1) {
                dis[v] = dis[u] + 1 ;
                fa[v] = u ;
                q.push(v) ;
            }
        }
    }
    int ans = s ;
    rep(i, 1, n) {
        if(dis[i] > dis[ans]) ans = i ;
    }
    return ans ;
}

int path[maxn] ;

void solve(){
    cin >> n ;
    rep(i, 1, n) {
        g[i].clear() ;
        deg[i] = 0 ;
    }
    rep(i, 1, n - 1) {
        int u, v ; cin >> u >> v ;
        g[u].pb(v) ; g[v].pb(u) ;
        deg[u] ++ ; deg[v] ++ ;
    }
    bool vis = 1 ;
    rep(i, 1, n) {
        if(deg[i] > 2) {
            vis = 0 ;
            break ;
        }
    }
    if(vis) {
        cout << -1 << endl ;
        return ;
    }
    int u = bfs(1), v = bfs(u) ;
    int len = 0 ;
    for(int x = v; x != -1; x = fa[x]) path[++ len] = x ;
    rep(i, 1, len / 2) swap(path[i], path[len - i + 1]) ;
    int a = -1, b = -1, c = -1 ;
    rep(i, 2, len - 1) {
        int x = path[i] ;
        if(deg[x] >= 3) {
            int pre = path[i - 1], nxt = path[i + 1], side = -1 ;
            for(auto y : g[x]) {
                if(y != pre && y != nxt) {
                    side = y ;
                    break ;
                }
            }
            if(side != -1) {
                a = pre ; b = x ; c = side ;
                break ;
            }
        }
    }
    cout << a << ' ' << b << ' ' << c << endl ;
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

::::

---

• 分类： OI
• 标签： 无标签