Naive Codes

LJOJ5214.cpp

// =================================
//   author: memset0
//   date: 2019.02.14 14:37:16
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
	x = 0; register char c = getchar(); register bool f = 0;
	while (!isdigit(c)) f ^= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	if (f) x = -x;
}
template <class T> inline void print(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline T max4(const T &a, const T &b, const T &c, const T &d) {
	return std::max(std::max(a, b), std::max(c, d));
}

const int N = 1e5 + 10;
int n, m, pos;
ll ans, s[N], dep[N];
int siz[N], fa[N], het[N], tov[N], id[N], wid[N], top[N], son[N];
int tot = 2, hed[N], nxt[N << 1], val[N << 1], to[N << 1];

void dfs1(int u) {
	siz[u] = 1;
	for (int i = hed[u], v; v = to[i], i; i = nxt[i])
		if (v != fa[u]) {
			fa[v] = u, het[v] = het[u] + 1, dep[v] = dep[u] + val[i], tov[v] = val[i], dfs1(v);
			siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v;
		}
}

void dfs2(int u, int tpt) {
	top[u] = tpt, id[u] = ++pos, wid[id[u]] = u;
	if (siz[u] == 1) return;
	dfs2(son[u], top[u]);
	for (int i = hed[u], v; v = to[i], i; i = nxt[i])
		if (v != fa[u] && v != son[u]) dfs2(v, v);
}

inline ll ask(int l, int r) { return s[r] - s[l - 1]; }
inline ll get_dis(int u, int v) {
	if (!u || !v) return 0;
	ll ans = 0;
	while (top[u] != top[v]) {
		if (het[top[u]] > het[top[v]]) std::swap(u, v);
		ans += ask(id[top[v]], id[v]), v = fa[top[v]];
	} ans += dep[u] < dep[v] ? ask(id[u] + 1, id[v]) : ask(id[v] + 1, id[u]);
	return ans;
}

struct info {
	int a, b;
} zero, q[N];
std::vector <info> list[N];

struct answer {
	info u, v; ll w; answer() {}
	inline bool operator < (const answer &other) const { return w < other.w; }
	inline bool operator > (const answer &other) const { return w > other.w; }
	inline answer (const info &x, const info &y) {
		u = x, v = y; w = dep[u.a] + dep[v.a] + get_dis(u.b, v.b);
		// printf("init. {%d %d} {%d %d} => %lld %lld %lld\n", u.a, u.b, v.a, v.b, dep[u.a], dep[v.a], get_dis(u.b, v.b));
	}
	friend inline answer merge(answer a, answer b) {
		answer ans = max4(answer(a.u, b.u), answer(a.u, b.v), answer(a.v, b.u), answer(a.v, b.v));
		// printf("{{%d %d}{%d %d}%lld} + {{%d %d}{%d %d}%lld} => {{%d %d}{%d %d}%lld}\n",
		// 	a.u.a, a.u.b, a.v.a, a.v.b, a.w, b.u.a, b.u.b, b.v.a, b.v.b, b.w, ans.u.a, ans.u.b, ans.v.a, ans.v.b, ans.w);
		return ans;
	}
} f[N];

void solve(int u) {
	for (auto it : list[u]) {
		f[u] = std::max(f[u], std::max(answer(f[u].u, it), answer(f[u].v, it)));
		// printf("[%d] => %d %d\n", u, it.a, it.b);
	}
	for (int i = hed[u], v; v = to[i], i; i = nxt[i]) if (v != fa[u]) {
		solve(v), f[u] = std::max(f[u], merge(f[u], f[v]));
	}
	if (f[u].u.a && f[u].v.a) ans = std::max(ans, f[u].w - (dep[u] << 1));
}

void main() {
	read(n), read(m);
	for (int i = 1, u, v, w; i < n; i++) {
		read(u), read(v), read(w);
		nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
		nxt[tot] = hed[v], to[tot] = u, val[tot] = w, hed[v] = tot++;
	} het[1] = 1, dep[1] = 1, dfs1(1), dfs2(1, 1);
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + tov[wid[i]];
	for (int i = 1, a, b; i <= m; i++) read(a), read(b), list[a].push_back((info){a, b});
	solve(1), print(ans, '\n');
	for (int i = 1; i <= n; i++) printf("{%d %d} {%d %d} %lld | %lld\n", f[i].u.a, f[i].u.b, f[i].v.a, f[i].v.b, f[i].w, dep[i] << 1);
}

} signed main() { return ringo::main(), 0; }

/*
4 4
1 3 4
3 4 2
4 2 3
1 2
1 1
4 4
4 1
*/