初HL分解です。
http://codeforces.com/contest/827/problem/D
解法自体は簡単で、ある辺について、それを含むループの中の辺での最大cost-1が答えとなる。
これはMSTを作ってHL分解すればできる。
snukeさんのコードを参考にした。
HL以外のところでめちゃくちゃバグらせた。
struct UF {
vector<int> par, ran;
void init(int n) {
par.resize(n); ran.resize(n);
for(int i = 0; i < n; i++) {
par[i] = i;
ran[i] = 0;
}
}
UF(int mx = 0) { init(mx); }
int find(int x) {
if(par[x] == x) return x;
else return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
if(ran[x] < ran[y]) {
par[x] = y;
}
else {
par[y] = x;
if(ran[x] == ran[y]) ran[x]++;
}
}
bool same(int x, int y) { return find(x) == find(y); }
};
struct segtree{
int n; vi sum, lazy;
void init(int mx) {
n = 1;
while(n < mx) n *= 2;
sum = vi(n * 2, -inf);
lazy = vi(n * 2, -inf);
}
segtree(int mx = 0) { init(mx); }
inline void lazy_eval(int k, int l, int r) {
if(lazy[k] != -inf) {
MAX(sum[k * 2 + 1], lazy[k]);
MAX(lazy[k * 2 + 1], lazy[k]);
MAX(sum[k * 2 + 2], lazy[k]);
MAX(lazy[k * 2 + 2], lazy[k]);
lazy[k] = -inf;
}
}
void app(int a, int b, ll s, int k, int l, int r) {
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
MAX(sum[k], s);
MAX(lazy[k], s);
}
else {
lazy_eval(k, l, r);
app(a, b, s, k * 2 + 1, l, (l + r) / 2);
app(a, b, s, k * 2 + 2, (l + r) / 2, r);
sum[k] = max(sum[k * 2 + 1], sum[k * 2 + 2]);
}
}
ll ga(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) return -inf;
if(a <= l && r <= b) return sum[k];
else {
lazy_eval(k, l, r);
ll lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
ll rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
return max(lv, rv);
}
}
ll get(int a, int b) { return ga(a, b, 0, 0, n); }
void update(int a, int b, ll s) { app(a, b, s, 0, 0, n); }
};
struct HL {
int n;
vector<vi> to, cost, D;
vi vcost, vd, vk, pv, dep;
vector<segtree> S;
vector<segtree> S2;
int root;
HL(int mx = 0): n(mx), to(mx), cost(mx), vcost(mx), vd(mx), vk(mx), dep(mx) {}
void add(int a, int b, int c = 1) {
to[a].pb(b); cost[a].pb(c);
to[b].pb(a); cost[b].pb(c);
}
int dfs(int v, int depth = 0, int p = -1) {
dep[v] = depth;
vector<pi> rs;
rep(i, 0, sz(to[v])) {
int u = to[v][i];
if(u == p) continue;
vcost[u] = cost[v][i];
rs.pb(pi(dfs(u, depth + 1, v), u));
}
if(sz(rs)) {
sort(all(rs));
vd[v] = vd[rs[0].sec]; pv[vd[v]] = p;
D[vd[v]].pb(v); vk[v] = -sz(D[vd[v]]);
return rs[0].fst - (sz(rs) != 1 && rs[0].fst == rs[1].fst);
}
else {
vd[v] = sz(D); vk[v] = -1; D.pb(vi(1, v)); pv.pb(p);
return 1;
}
}
void init(int v = 0) {
root = v;
dfs(root);
rep(i, 0, sz(D)) reverse(all(D[i]));
rep(i, 0, sz(vk)) vk[i] += sz(D[vd[i]]);
rep(i, 0, sz(D)) {
S.pb(segtree(sz(D[i])));
S2.pb(segtree(sz(D[i])));
rep(j, 0, sz(D[i])) S[i].update(j, j + 1, vcost[D[i][j]]);
}
}
int lca(int a, int b) {
int p = vd[a]; vi ap(1, p);
while(pv[p] != -1) ap.pb(p = vd[pv[p]]);
reverse(all(ap)); ap.pb(-1);
p = vd[b]; vi bp(1, p);
while(pv[p] != -1) bp.pb(p = vd[pv[p]]);
reverse(all(bp)); bp.pb(-2);
int pi = 1; while(ap[pi] == bp[pi]) pi++;
p = ap[pi - 1];
int ai = vd[a] == p ? vk[a] : vk[pv[ap[pi]]];
int bi = vd[b] == p ? vk[b] : vk[pv[bp[pi]]];
return D[p][min(ai, bi)];
}
ll ga(int par, int v) {
ll res = -inf;
while(true) {
int nd = vd[v], nk = vk[v];
if(nd == vd[par]) {
return max(res, S[nd].get(vk[par] + 1, nk + 1));
}
else {
MAX(res, S[nd].get(0, nk + 1));
}
v = pv[nd];
}
}
void app(int par, int v, ll x) {
while(true) {
int nd = vd[v], nk = vk[v];
if(nd == vd[par]) {
S2[nd].update(vk[par] + 1, nk + 1, -x);
return;
}
else {
S2[nd].update(0, nk + 1, -x);
}
v = pv[nd];
}
}
int query(int a, int b, ll x) {
int par = lca(a, b);
ll res =ga(par, a);
MAX(res, ga(par, b));
app(par, a, max(res, x));
app(par, b, max(res, x));
return res;
}
int get(int a, int b) {
if(dep[a] < dep[b]) a = b;
return -S2[vd[a]].get(vk[a], vk[a] + 1);
}
};
struct edge {
int a, b, c, i;
bool operator<(const edge& e) {
return c < e.c;
}
};
int N, M;
edge es[MAX_N];
int ans[MAX_N];
void solve() {
cin >> N >> M;
rep(i, 0, M) {
int a, b, c;
cin >> a >> b >> c; a--; b--;
es[i] = (edge){a, b, c, i};
}
UF uf(N);
sort(es, es + M);
HL g(N);
rep(i, 0, M) {
int a = es[i].a, b = es[i].b, c = es[i].c, at = es[i].i;
if(!uf.same(a, b)) {
uf.unite(a, b);
ans[at] = -1;
g.add(a, b, c);
}
}
g.init();
rep(i, 0, M) {
int a = es[i].a, b = es[i].b, c = es[i].c, at = es[i].i;
if(ans[at] == -1) continue;
ans[at] = g.query(a, b, c);
}
rep(i, 0, M) {
int a = es[i].a, b = es[i].b, at = es[i].i;
if(ans[at] != -1) continue;
ans[at] = g.get(a, b);
}
rep(i, 0, M) {
if(ans[i] == inf) {
cout << -1 << "\n";
}
else {
cout << ans[i] - 1 << "\n";
}
}
}
UF+segtree+LCA+HLdecですごいエグイ感じになってて楽しい。
doublingのLCA+sparse tableっぽいものでもできる。そっちも実装したいね。
