< syun0713さんのAI生成コード置き場

HLD wip

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

①逆元が存在しない場合
②交換法則が成り立たない場合
③遅延セグ木にする場合
はオイラーツアーでは解けないためHL分解で解く

//https://judge.yosupo.jp/submission/411186
//https://judge.yosupo.jp/submission/411201
struct HLD {
	int n;
	vi pa, depth, sb, hch;//sb:部分木の頂点数 hch:heavy child
	vvi g, ch;
	vi v;//v[i]=heavy child優先でDFSしてi番目に訪れる頂点 heavy pathはv上で一列に並んでいる
	vi id;//id[i]=heavy child優先でDFSして頂点iを何番目に訪れるか(vの逆関数)
	vi head;//head[i]=頂点iを通るheavy pathの一番上の頂点
	static pair<S, S> op2(pair<S, S> a, pair<S, S> b) { return { op(a.fi,b.fi),op(b.se,a.se) }; }
	static pair<S, S> e2() {return { e(),e()};}
	segtree<pair<S,S>, op2, e2> seg;
	int edge_cnt; bool is_built;
	bool is_edge; // ★追加: 辺に値を持つかどうか
	HLD(int n, bool is_edge) : n(n), g(n), pa(n, -1), ch(n), depth(n, 0), sb(n, 1), hch(n, -1), v(n), id(n), head(n), seg(n), edge_cnt(0), is_built(0), is_edge(is_edge) {}
	void add_edge(int u, int v) {
		edge_cnt++;
		assert(0 <= u && u < n && 0 <= v && v < n);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build() {
		assert(edge_cnt == n - 1 && is_built == 0);
		is_built = 1;
		auto dfs0 = [&](auto& self, int s)->void {
			int h = -1;//現在のheavy child候補を根とする部分木の頂点数
			for (auto i : g[s]) if (i != pa[s]) {//sの子i全てに対して
				pa[i] = s;
				ch[s].pb(i);
				depth[i] = depth[s] + 1;
				self(self,i);
				sb[s] += sb[i];
				if (chmax(h, sb[i])) hch[s] = i;
			}
			};
		int cnt = 0;//今までに訪れた頂点数
		auto dfs1 = [&](auto& self, int s)->void {
			v[cnt] = s;
			id[s] = cnt;
			cnt++;
			if (s != 0 && hch[pa[s]] == s) head[s] = head[pa[s]];
			else head[s] = s;
			if (hch[s] != -1)self(self,hch[s]);
			for (auto i : g[s]) if (i != pa[s] && i != hch[s]) {
				self(self,i);
			}
			};
		dfs0(dfs0,0);
		dfs1(dfs1,0);
	}
	int pn(int a, int x) {//aのx個上の先祖 存在しないなら-1 O(logN)
		assert(0 <= a && a < n && 0 <= x && is_built);
		int td = depth[a] - x;
		if (td < 0) return -1;
		while (a != -1) {
			if (depth[head[a]] <= td) return v[id[head[a]] + td - depth[head[a]]];
			a = pa[head[a]];
		}
		return -1;
	};
	int lca(int a, int b) {//a,bのlca O(logN)
		assert(0 <= a && a < n && 0 <= b && b < n && is_built);
		while (head[a] != head[b]) {
			if (id[a] > id[b]) swap(a, b);
			b = pa[head[b]];
		}
		if (id[a] > id[b]) return b;
		return a;
	}
	int dist1(int a, int b) {//頂点aからbの間の辺の数
		assert(is_built);
		return depth[a] + depth[b] - 2 * depth[lca(a, b)];
	}
	int jump(int a, int b, int k) {//パス{a,...,b}におけるk番目の頂点(k==0のときa) 存在しなければ-1
		assert(is_built);
		int l = lca(a, b);
		int dist = depth[a] + depth[b] - 2 * depth[l];
		if (dist < k) return -1;
		if (depth[a] - depth[l] >= k) {
			return pn(a, k);
		}
		else return pn(b, dist - k);
	}
	void sset(int i, S x) {//頂点iにxをset
		assert(is_built);
		seg.set(id[i], { x,x });
	}
	S sget(int i) {//頂点iをget
		return seg.get(id[i]).fi;
	}
	S sprod(int a, int b) {//パス{a,...,b}に対してこの順での総opを計算 (半開区間ではない)
		S ans_up = e();
		S ans_down = e();
		while (head[a] != head[b]) {
			if (depth[head[a]] > depth[head[b]]) {
				ans_up = op(ans_up, seg.prod(id[head[a]], id[a] + 1).se);
				a = pa[head[a]];
			}
			else {
				ans_down = op(seg.prod(id[head[b]], id[b] + 1).fi, ans_down);
				b = pa[head[b]];
			}
		}
		if (depth[a] > depth[b]) {
			ans_up = op(ans_up, seg.prod(id[b] + (is_edge ? 1 : 0), id[a] + 1).se); // ★修正
		}
		else {
			ans_down = op(seg.prod(id[a] + (is_edge ? 1 : 0), id[b] + 1).fi, ans_down); // ★修正
		}
		return op(ans_up, ans_down);
	}
	S subtree_prod(int u) { // ★追加
		assert(is_built);
		int l = id[u] + (is_edge ? 1 : 0);
		int r = id[u] + sb[u];
		if (l >= r) return e();
		return seg.prod(l, r).fi;
	}
};


//lazyseg
struct HLD {
	int n;
	vi pa, depth, sb, hch;//sb:部分木の頂点数 hch:heavy child
	vvi g, ch;
	vi v;//v[i]=heavy child優先でDFSしてi番目に訪れる頂点 heavy pathはv上で一列に並んでいる
	vi vid;//id[i]=heavy child優先でDFSして頂点iを何番目に訪れるか(vの逆関数)
	vi head;//head[i]=頂点iを通るheavy pathの一番上の頂点
	static pair<S, S> op2(pair<S, S> a, pair<S, S> b) { return { op(a.fi,b.fi),op(b.se,a.se) }; }
	static pair<S, S> e2() { return { e(),e() }; }
	//segtree<pair<S,S>, op2, e2> seg;
	static pair<S, S> mapping2(F x, pair<S, S> a) { return { mapping(x,a.fi),mapping(x,a.se) }; }
	lazy_segtree<pair<S, S>, op2, e2, F, mapping2, composition, id> seg;

	int edge_cnt; bool is_built;
	bool is_edge;
	HLD(int n, bool is_edge) : n(n), g(n), pa(n, -1), ch(n), depth(n, 0), sb(n, 1), hch(n, -1), v(n), vid(n), head(n), seg(n), edge_cnt(0), is_built(0), is_edge(is_edge) {}
	void add_edge(int u, int v) {
		edge_cnt++;
		assert(0 <= u && u < n && 0 <= v && v < n);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build() {
		assert(edge_cnt == n - 1 && is_built == 0);
		is_built = 1;
		auto dfs0 = [&](auto& self, int s)->void {
			int h = -1;//現在のheavy child候補を根とする部分木の頂点数
			for (auto i : g[s]) if (i != pa[s]) {//sの子i全てに対して
				pa[i] = s;
				ch[s].pb(i);
				depth[i] = depth[s] + 1;
				self(self, i);
				sb[s] += sb[i];
				if (chmax(h, sb[i])) hch[s] = i;
			}
			};
		int cnt = 0;//今までに訪れた頂点数
		auto dfs1 = [&](auto& self, int s)->void {
			v[cnt] = s;
			vid[s] = cnt;
			cnt++;
			if (s != 0 && hch[pa[s]] == s) head[s] = head[pa[s]];
			else head[s] = s;
			if (hch[s] != -1)self(self, hch[s]);
			for (auto i : g[s]) if (i != pa[s] && i != hch[s]) {
				self(self, i);
			}
			};
		dfs0(dfs0, 0);
		dfs1(dfs1, 0);
	}
	int pn(int a, int x) {//aのx個上の先祖 存在しないなら-1 O(logN)
		assert(0 <= a && a < n && 0 <= x && is_built);
		int td = depth[a] - x; 
		if (td < 0) return -1;
		while (a != -1) {
			if (depth[head[a]] <= td) return v[vid[head[a]] + td - depth[head[a]]];
			a = pa[head[a]];
		}
		return -1;
	};
	int lca(int a, int b) {//a,bのlca O(logN)
		assert(0 <= a && a < n && 0 <= b && b < n && is_built);
		while (head[a] != head[b]) {
			if (vid[a] > vid[b]) swap(a, b);
			b = pa[head[b]];
		}
		if (vid[a] > vid[b]) return b;
		return a;
	}
	int dist1(int a, int b) {//頂点aからbの間の辺の数
		assert(is_built);
		return depth[a] + depth[b] - 2 * depth[lca(a, b)]; 
	}
	int jump(int a, int b, int k) {//パス{a,...,b}におけるk番目の頂点(k==0のときa) 存在しなければ-1
		assert(is_built);
		int l = lca(a, b);
		int dist = depth[a] + depth[b] - 2 * depth[l];
		if (dist < k) return -1;
		if (depth[a] - depth[l] >= k) { 
			return pn(a, k);
		}
		else return pn(b, dist - k);
	}
	void sset(int i, S x) {//頂点iにxをset
		assert(is_built);
		seg.set(vid[i], { x,x });
	}
	S sget(int i) {//頂点iをget
		return seg.get(vid[i]).fi;
	}
	S sprod(int a, int b) {//パス{a,...,b}に対してこの順での総opを計算 (半開区間ではない)
		S ans_up = e();
		S ans_down = e();
		while (head[a] != head[b]) {
			if (depth[head[a]] > depth[head[b]]) {
				ans_up = op(ans_up, seg.prod(vid[head[a]], vid[a] + 1).se);
				a = pa[head[a]];
			}
			else {
				ans_down = op(seg.prod(vid[head[b]], vid[b] + 1).fi, ans_down);
				b = pa[head[b]];
			}
		}
		if (depth[a] > depth[b]) {
			ans_up = op(ans_up, seg.prod(vid[b] + (is_edge ? 1 : 0), vid[a] + 1).se);
		}
		else {
			ans_down = op(seg.prod(vid[a] + (is_edge ? 1 : 0), vid[b] + 1).fi, ans_down);
		}
		return op(ans_up, ans_down);
	}
	void sapply(int a, int b, F f) {//パス{a,...,b}に対してfをapply (半開区間ではない)
		while (head[a] != head[b]) {
			if (depth[head[a]] > depth[head[b]]) {
				seg.apply(vid[head[a]], vid[a] + 1, f);
				a = pa[head[a]];
			}
			else { 
				seg.apply(vid[head[b]], vid[b] + 1, f);
				b = pa[head[b]];
			}
		}
		if (depth[a] > depth[b]) {
			seg.apply(vid[b] + (is_edge ? 1 : 0), vid[a] + 1, f);
		}
		else {
			seg.apply(vid[a] + (is_edge ? 1 : 0), vid[b] + 1, f);
		}
	}
	S subtree_prod(int u) {
		assert(is_built);
		int l = vid[u] + (is_edge ? 1 : 0);
		int r = vid[u] + sb[u];
		if (l >= r) return e();
		return seg.prod(l, r).fi;
	}
	void subtree_apply(int u, F f) {
		assert(is_built);
		int l = vid[u] + (is_edge ? 1 : 0);
		int r = vid[u] + sb[u];
		if (l < r) seg.apply(l, r, f);
	}
};