2016-2017 ACM-ICPC Asia-Bangkok Regional Contest E ACM Tax

問題ページ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270 のL番目を中央値に変更したものであるが，複数テストケースで15ケースあってTLが厳しくなっている．HL分解 + BIT でlog3つ，並列二分探索 + 辺重みを変更できるLCA でlog2つの解はあるがTLEしそうなので https://www.utpc.jp/2011/slides/l_th.pdf のlog1つの解を実装する．

L番目の数が何か求めるには決め打ち二分探索がよくある方法で，これを行うにはパス上に 以下の数が何個あるか？というクエリに高速に答えられれば良い．パス 上の 以下の数の個数は (根から までの 以下の個数) + (根から までの 以下の個数) - 2*(根から のLCAまでの 以下の個数) で求められる．したがって各頂点から根までの間に 以下の数が何個あるか？を高速に求められればよい．

各頂点に根までに存在する整数の個数を記録した二分探索木をもたせる．これは明らかにMLE/TLEするが，親の頂点の二分探索木と比べ，1要素増えているだけなので変化する要素が少ない．したがって，永続データ構造の要領でデータを管理することでMLE/TLEを回避できる．二分探索木の形を決定しておくと，実質永続セグ木にすることができ，永続平衡二分探索木と比べて実装を簡略化できる．

以下の個数が 個以上存在するような最大の を求めるには二分探索木を下にたどっていけばいい．パス とそのLCAの3頂点で並列にそれぞれ二分探索木を下にたどっていくことで求められる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
struct LCA {  
    const int n = 0;  
    const int log2_n = 0;  
    vector<vector<int>> g;  
    vector<vector<int>> par;  // par[2^i上][頂点v]  
    vector<int> dep;  
  
    void dfs(int v, int p, int d) {  
        par[0][v] = p;  
        dep[v] = d;  
        for(auto to: g[v]) {  
            if(to == p) continue;  
            dfs(to, v, d+1);  
        }  
    }  
  
    LCA() {}  
    LCA(int n) : n(n), log2_n(log2(n)+1), g(n),  
        par(log2_n, vector<int>(n)), dep(n) {}  
  
    void add_edge(int u, int v) {  
        g[u].push_back(v);  
        g[v].push_back(u);  
    }  
  
    void build(ll root=0) {  
        dfs(root, -1, 0);  
        for(int i=0; i+1 < log2_n; ++i) {  
            for(int j = 0; j < n; ++j) {  
                if(par[i][j] < 0) par[i+1][j] = -1;  
                else par[i+1][j] = par[i][par[i][j]];  
            }  
        }  
    }  
  
    int get(int u, int v) {  
        if(dep[u] > dep[v]) swap(u, v);  
        REP(i, log2_n) {  
            if((dep[v] - dep[u]) >> i & 1) {  
                v = par[i][v];  
            }  
        }  
        if(u == v) return u;  
        for(int i=log2_n-1; i>=0; --i) {  
            if(par[i][u] != par[i][v]) {  
                u = par[i][u];  
                v = par[i][v];  
            }  
        }  
        return par[0][u];  
    }  
};  
  
int pos, l[50010*20], r[50010*20], val[50010*20];  
int ins(int x, int a, int b, int c) {  
    int y = ++pos;  
    val[pos] = val[x] + 1;  
    if(a == b) return y;  
    int mid = (a+b)/2;  
    if(c <= mid) {  
        l[y] = ins(l[x], a, mid, c);  
        r[y] = r[x];  
    } else {  
        l[y] = l[x];  
        r[y] = ins(r[x], mid+1, b, c);  
    }  
    return y;  
}  
  
int rt[50010], dep[50010];  
vector<PII> g[50010];  
void dfs(int v, int p) {  
    for(auto to: g[v]) {  
        if(to.first == p) continue;  
        dep[to.first] = dep[v] + 1;  
        rt[to.first] = ins(rt[v], 1, 100000, to.second);  
        dfs(to.first, v);  
    }  
}  
  
int kth(int x, int y, int z, int k) {  
    int lb = 1, ub = 100000;  
    while(lb<ub) {  
        int mid = (lb+ub)/2;  
        int t = val[l[x]] + val[l[y]] - 2*val[l[z]];  
        if(k <= t) {  
            ub = mid;  
            x = l[x], y = l[y], z = l[z];  
        } else {  
            lb = mid+1, k -= t;  
            x = r[x], y = r[y], z = r[z];  
        }  
    }  
    return lb;  
}  
  
void solve() {  
    int n;  
    cin >> n;  
    LCA lca(n);  
    REP(i, n-1) {  
        int a, b, c;  
        cin >> a >> b >> c;  
        a--, b--;  
        lca.add_edge(a, b);  
        g[a].push_back({b, c});  
        g[b].push_back({a, c});  
    }  
    lca.build();  
    dep[0] = 0;  
    dfs(0, -1);  
  
    int q;  
    cin >> q;  
    REP(i, q) {  
        int a, b;  
        cin >> a >> b;  
        a--, b--;  
  
        int p = lca.get(a, b);  
        int dist = dep[a] + dep[b] - 2*dep[p];  
        if(dist%2) {  
            int ret = kth(rt[a], rt[b], rt[p], (dist+1)/2);  
            cout << ret << ".0" << endl;  
        } else {  
            int ret = kth(rt[a], rt[b], rt[p], dist/2) + kth(rt[a], rt[b], rt[p], dist/2+1);  
            cout << ret/2 << "." << (ret%2?5:0) << endl;  
        }  
    }  
  
    REP(i, n) {  
        g[i].clear();  
        rt[i] = 0;  
    }  
    REP(i, pos+1) l[i] = r[i] = val[i] = 0;  
    pos = 0;  
}  
  
int main(void) {  
    cin.tie(0);  
    ios::sync_with_stdio(false);  
  
    int t;  
    cin >> t;  
    while(t--) solve();  
  
    return 0;  
}  
``