Codeforces Round #423D: Best Edge Weight

初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]);//if range_min, erase (m - l)
			MAX(lazy[k * 2 + 1], lazy[k]);
			MAX(sum[k * 2 + 2], lazy[k]);//here too
			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); //here too
			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); } //[a, b)
	void update(int a, int b, ll s) { app(a, b, s, 0, 0, n); } //[a, b)
};

struct HL {
	int n;
	vector<vi> to, cost, D;//D:group
	vi vcost, vd, vk, pv, dep;//vcost:edge cost,vd:D at,vk:num from parent,pv:group par,dep:depth
	vector<segtree> S; //change 
	vector<segtree> S2; //change
	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])));//change
			rep(j, 0, sz(D[i])) S[i].update(j, j + 1, vcost[D[i][j]]); //change
		}
	}
	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)];
	}

	//////////////////////////////////////////////////////////////////////////////from here change
	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っぽいものでもできる。そっちも実装したいね。