萌新刚学 LCT, $毒\ 瘤\ R\ E\ 求\ 助$
查看原帖
萌新刚学 LCT, $毒\ 瘤\ R\ E\ 求\ 助$
75765
Starlight237楼主2020/8/7 16:04

(样例过了)

#include<bits/stdc++.h>
using namespace std;
#define reg register
extern "C" {
namespace io{
#define BUFS 100000
	static char in[BUFS], *p = in, *pp = in;
#define gc() (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
	inline char gtc() {while (isspace(*p)) ++p; return *p++;}
	inline int read() {
		reg int x = 0; reg char ch, f = 0;
		while (!isdigit(ch = gc())) f |= ch == '-';
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return f ? -x : x;
	}
}}
#define rd io :: read
const int N = 200001, inf = 0x3f3f3f3f;
int n, tot, head[N], ans = -inf;
struct Edge{int v, w, nxt;} eg[N << 1];
inline void addedge(int u, int v, int w) {
	eg[++tot] = Edge{v, w, head[u]}, head[u] = tot;
}
inline int fir(multiset<int>&s) {return s.size() ? *s.rbegin() : -inf;}
inline int sec(multiset<int>&s) {return s.size() > 1 ? *(++s.rbegin()) : -inf;}
multiset<int> chn[N], pth[N];
struct Node {
	int val, col, umx, dmx, dmt, sum, len;
	Node *fa, *ch[2];
	Node();
}spl[N], *null = spl;
Node :: Node() {fa = ch[0] = ch[1] = spl, umx = dmx = dmt = -inf;}
inline bool nroot(Node *x) {return x -> fa -> ch[0] == x || x -> fa -> ch[1] == x;}
inline void pushup(Node *x) {
	int vir = max(x -> val, fir(chn[x - spl])),
	L = max(vir, x -> ch[0] -> dmx + x -> len),
	R = max(vir, x -> ch[1] -> umx);
	x -> umx = max(x -> ch[0] -> umx, x -> ch[0] -> sum + x -> len + R),
	x -> dmx = max(x -> ch[1] -> dmx, x -> ch[1] ->sum + L),
	x -> dmt = max(x -> ch[0] -> dmx + x -> len + R, x -> ch[1] -> umx + L);
	x -> dmt = max(x -> dmt, max(x -> ch[0] -> dmt, x -> ch[1] -> dmt)),
	x -> dmt = max(x -> dmt, fir(pth[x - spl])),
	x -> dmt = max(x -> dmt, fir(chn[x - spl]) + sec(chn[x - spl])),
	x -> val || (x -> dmt = max(x -> dmt, max(fir(chn[x - spl]), 0)));
}
inline void rotate(Node *x) {
	reg Node *y = x -> fa, *z = y -> fa; reg int k = y -> ch[1] == x;
	nroot(y) && (z -> ch[z -> ch[1] == y] = x, 0), x -> fa =z;
	y -> ch[k] = x -> ch[k ^ 1], x -> ch[k ^ 1] -> fa = y;
	x -> ch[k ^ 1] = y, y -> fa = x;
	pushup(y), pushup(x);
}
inline void splay(Node *x) {
	for (reg Node *y, *z; nroot(x); rotate(x))
		y = x -> fa, z = y -> fa,
		nroot(y) && (rotate((z -> ch[0] == y) ^ (y -> ch[0] == x)? x : y), 0);
}
inline void access(Node *x) {
	for (reg Node *y = null; x != null; y = x, x = x -> fa)
		splay(x),
		x -> ch[1] != null && (pth[x - spl].insert(x -> ch[1] -> dmt), chn[x - spl].insert(x -> ch[1] -> umx), 0),
		y != null && (pth[x - spl].erase(pth[x - spl].find(y -> dmt)), chn[x - spl].erase(chn[x - spl].find(y -> umx)), 0),
		x -> ch[1] = y, pushup(x);
}
inline void modify(Node *x) {
	access(x), splay(x);
	x -> col ^= 1, x -> val = x -> col ? -inf : 0;
	pushup(x), ans = x -> dmt;
}
void dfs(int x, int Fa) {
	(spl + x) -> fa = spl + Fa;
	for (reg int i = head[x], v; i; i = eg[i].nxt)
		(v = eg[i].v) != Fa && (
			(spl + v) -> len = eg[i].w,
			dfs(v, x),
			chn[x].insert((spl + v) -> umx), pth[x].insert((spl + v) -> dmt), 0
		);
	pushup(spl + x);
}
int main() {
	n = rd();
	for (reg int i = 1, u, v, w; i < n; ++i)
		u = rd(), v = rd(), w = rd(),
		addedge(u, v, w), addedge(v, u, w);
	dfs(1, 0);
	ans = (spl + 1) -> dmt;
	for (reg int q = rd(); q; --q) {
		char op; int x;
		op = io :: gtc();
		op == 'A' ? ans < 0 ? puts("They have disappeared."), 0 : printf("%d\n", ans) : (x = rd(), modify(spl + x), 0);
	}
	return 0;
}
2020/8/7 16:04
加载中...