mayoko’s diary

プロコンとかいろいろ。

RUPC Day1 F : Relay

AOJ

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=F

解法

解説スライドを参考にして解きました。

普通に解こうとすると, 以下のようになります。

どこの辺を切るかで場合分けする
一本の辺を切った場合, グラフは２つの木に分かれる。そのそれぞれについて, 木の直径を求め, (2 つのうち直径の大きい方) + (切った辺の長さ) の max 値が答え

これでやると, 辺を切る場所が N-1 通り, それぞれの場合に直径を求めるのにかかる時間が O(N) で, 計算量は O(N^2) です。これを高速化したいんですが, 結局直径の両端からの深さだけを調べれば良い, ということになります。

直径の両端の点を (u, v) とします。切る辺で, 場合分けをしましょう。u を根とした木を考えることにします。

直径で使われる辺以外を切る場合

この場合は u-v パスがあるので(直径) + (切る辺) で OK です。

u-v パスで, 中心よりも葉側の辺を切る場合

(e.from, e.to) という辺を切ったとします。

この場合は, u から最長の点 x を調べて, u-x と切った辺をつなげるのが最適になります。
u - (中心) - e.from というようなパスは残っていることになり, これを使って u - (中心) - e.from - x とするのが良いということですが, これはなぜかというと,
u-(中心) のところは別の頂点 y を使って y-(中心)とかやらないほうが良いです。これは, 中心から見ると u が最長距離の頂点になっているからです。これは pekempey さんの記事を見るとわかりやすいと思います。
pekempey.hatenablog.com
なので, u - (中心) - e.from というパスをつかわないとすると, (中心の子) - (中心) - (中心の子) というようにパスをつなぐのが残りの候補ですが, (中心) - (中心の子) というパスは, (中心) - u というパスと等しいか短いので, やはり u は使ったほうが得です。

ということで, u - (中心) - e.from - x とするのが良いです。

u-v パスで, 中心よりも根側の辺を切る場合

u と v の立場を入れ替えて, 同様に考えれば良いです。

ということで, u からひとつの辺を取り除いた時の最長パス, v からひとつの辺を取り除いた時の最長パスを高速で求められれば良くなりました。これは, オイラーツアー上のセグメント木を使えば簡単に求められます。
ある辺 (e.from, e.to) を切った場合, e.to の部分木にアクセス出来ないようにした場合の最大値を求めれば良いですね。

木の直径が必ず中心を通る, という性質を使うと見通しが良くなる問題でした。面白かったです。

// セグメント木(RMQ 対応)
// update: k 番目の値を a に変更
// query: [l, r) の区間の最大値を求める
template<typename T>
struct ST {
    vector<T> seg;
    int size;
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1, numeric_limits<T>::min());
    }
    inline T merge(T x, T y) {
        return max(x, y);
    }
    void update(int k, T a) {
        k += size-1;
        seg[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            seg[k] = merge(seg[k*2+1], seg[k*2+2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return numeric_limits<T>::min();
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

// Euler-Tour
const int MAXSIZE = 200020;
int BEGIN[MAXSIZE], END[MAXSIZE];
vector<int> euler_tour;
int K;

struct edge {
    int to;
    int cost;
    edge() {}
    edge(int to, int cost) : to(to), cost(cost) {}
};

vector<vector<edge> > G;

void createEulerTour(int v, int p) {
    BEGIN[v] = K++;
    euler_tour.push_back(v);
    for (edge e : G[v]) {
        if (e.to == p) continue;
        createEulerTour(e.to, v);
        euler_tour.push_back(v);
        K++;
    }
    END[v] = K;
}

typedef pair<int, int> Result;
Result visit(int p, int v, const vector<vector<edge> >& g) {
    Result r(0, v);
    for (edge e : g[v]) if (e.to != p) {
        Result t = visit(v, e.to, g);
        t.first += e.cost;
        if (r.first < t.first) r = t;
    }
    return r;
}

// 直径を構成する２つの頂点 (u, v) を返す
pii diameter(const vector<vector<edge> >& g) {
    Result r = visit(-1, 0, g);
    Result t = visit(-1, r.second, g);
    return pii(r.second, t.second);
}

void dfs(int v, int p, int d, vi& depth) {
    depth[v] = d;
    for (edge e : G[v]) if (e.to != p) {
        dfs(e.to, v, d+e.cost, depth);
    }
}

int calc(int s) {
    int n = G.size();
    vector<int> depth(n);
    dfs(s, -1, 0, depth);
    euler_tour.clear();
    K = 0;
    createEulerTour(s, -1);
    ST<int> seg(2*n);
    for (int i = 0; i < n; i++) seg.update(BEGIN[i], depth[i]);
    int ret = 0;
    for (int v = 0; v < n; v++) {
        for (edge e : G[v]) {
            int to = e.to;
            if (depth[e.to] < depth[v]) to = v;
            int tmp = max(seg.query(0, BEGIN[to]), seg.query(END[to], 2*n));
            ret = max(ret, tmp+e.cost);
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    G.resize(N);
    for (int i = 1; i < N; i++) {
        int p, w;
        cin >> p >> w;
        G[i].emplace_back(p, w);
        G[p].emplace_back(i, w);
    }
    pii dia = diameter(G);
    cout << max(calc(dia.first), calc(dia.second)) << endl;
    return 0;
}