Boj 13510) 트리와 쿼리 1

문제

백준 13510

설명

처음으로 푼 HLD 문제.

기록용으로 남긴다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}+\mathrm{M} \log^2{\mathrm{N}}\))

코드

template<typename T, size_t _H>
class SegmentTree
{
	template<typename F>
	struct Node {
		Node() {}
		Node(F v) : v(v) {}
		F operator+(const Node& in) { return max(v, in.v); }
		F v = 0;
	};

public:
	void Init() { for (int i = INDEX_MAX - 1; i > 0; i--) nodes[i] = nodes[i << 1] + nodes[i << 1 | 1]; }

	void Update(int i, const T& v) {
		for (i += INDEX_MAX - 1, nodes[i] = v; i > 1; i >>= 1)
			nodes[i >> 1].v = nodes[i] + nodes[i ^ 1];
	}

	Node<T> Query(int l, int r) {
		T rs = T();
		for (r += INDEX_MAX - 1, l += INDEX_MAX - 1; l <= r; r >>= 1, l >>= 1)
		{
			if (l & 1) rs = nodes[l++] + rs;
			if (!(r & 1)) rs = nodes[r--] + rs;
		}
		return rs;
	}

	Node<T> nodes[1 << _H];
	int INDEX_MAX = 1 << _H - 1;
};

const int MAX_IN = 100001;
int line2Idx[MAX_IN]; // line is a->b, then b
struct INPUT { int d, w, idx; };
std::vector<INPUT> inputs[MAX_IN];

struct HeavyLightDecomposition
{
	struct EDGE { int d, w; };
	SegmentTree<int, 18> seg;
	std::vector<EDGE> edges[MAX_IN];
	int sz[MAX_IN], depths[MAX_IN], parent[MAX_IN];
	int in[MAX_IN], out[MAX_IN], roots[MAX_IN];

	void DFS1(int v = 1)
	{
		sz[v] = 1;
		for (EDGE& e : edges[v])
		{
			depths[e.d] = depths[v] + 1;
			parent[e.d] = v;
			DFS1(e.d);
			sz[v] += sz[e.d];
			if (sz[e.d] > sz[edges[v][0].d])
				swap(e, edges[v][0]);
		}
	}

	int pv = 0;
	void DFS2(int v = 1)
	{
		in[v] = ++pv;
		for (EDGE& e : edges[v]) {
			roots[e.d] = e.d == edges[v][0].d ? roots[v] : e.d;
			DFS2(e.d);
			seg.nodes[seg.INDEX_MAX - 1 + in[e.d]] = e.w;
		}
		out[v] = pv;
	}

	void Init()
	{
		roots[1] = 1;
		DFS1();
		DFS2();
		seg.Init();
	}

	void Update(int v, int w)
	{
		seg.Update(in[v], w);
	}

	int Query(int a, int b)
	{
		int ret = 0;
		while (roots[a] ^ roots[b])
		{
			if (depths[roots[a]] < depths[roots[b]]) swap(a, b);
			ret = max(ret, seg.Query(in[roots[a]], in[a]).v);
			a = parent[roots[a]];
		}
		if (depths[a] > depths[b]) swap(a, b);
		ret = max(ret, seg.Query(in[a]+1, in[b]).v);
		return ret;
	}
} hld;

void Construct(int v = 1, int parent = -1)
{
	for (auto& l : inputs[v])
	{
		if (l.d == parent) continue;
		hld.edges[v].push_back({ l.d, l.w });		
		line2Idx[l.idx] = l.d;
		Construct(l.d, v);
	}
}

int main()
{
	int n; cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		inputs[a].push_back({ b, c, i });
		inputs[b].push_back({ a, c, i });
	}

	Construct();
	hld.Init();
	
	int T; cin >> T;
	while (T--)
	{
		int op, a, b; cin >> op >> a >> b;
		switch (op)
		{
		case 1: 
			// a 간선비용을 b 로 바꾼다 
			hld.Update(line2Idx[a], b);
			break; 
		case 2: // a->b 로 가는 비용중 가장 큰것
			cout << hld.Query(a, b) << '\n';
			break;
		}
	}
}