💪

【チャレンジ記録】競プロ典型 90 問_3問目

2022/01/07に公開

競技プログラミング

※勉強中のため、考察など後ほど付け加える可能性があります。

問題

考えたこと

木構造把握できたため、辺が一つのノードからの最長経路を求めようとしてしまった。
辺が一つのノードをランダムで選ぶ場合の最長経路だと、下記の図のような、選んだノードが最長経路上にないケースで最長とならない。

辺が一つのノードをランダムで選んだ場合

解答

間違った最長経路の求め方をしていたため、twitterの解説を見てから木の直径について理解して解答した。

下記記事がなぜ最長経路を2回で木の直径になるかを証明していて、参考になった。

#include <bits/stdc++.h>
#include <atcoder/all>
#include <vector>
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
#define ll long long
using namespace std;
using namespace atcoder;
const ll MX = 1e6;
const ll inf = 1e13;
const int mod = 1000000007;
int a[MX];
int v[MX];
int n;
vector<vector<int> > d;
int dfs(int xx, int depth) {
    v[xx]=1;
    a[xx]=depth;
    int mx = 1;
    for(int next: d[xx]) {
        if(v[next]==1) continue;
        mx = max(dfs(next, depth+1)+1,mx);
    }
    return mx;
}
signed main(){
    cin>>n;
    d.resize(n);
    rep(i,n-1) {
        int x,y;
        cin>>x>>y;
        x--; y--;
        d[x].push_back(y);
        d[y].push_back(x);
    }
    int mx = dfs(0, 1);
    int mxi = 0;
    rep(i,n){
        if(a[i]==mx) {
            mxi=i;
        }
    }
    rep(i,n) a[i]=v[i]=0;
    mx = dfs(mxi, 0);
    cout << mx << endl;
 
    return 0;
}

問題

考えたこと

解答

Discussion