救救孩子 T飞了RE疯了
查看原帖
救救孩子 T飞了RE疯了
235657
hwx12233楼主2020/8/15 22:56

RT

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <cassert>

using namespace std;

template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl

template <typename T> void read (T &x) {
	x = 0; bool f = 1; char ch;
	do {ch = getchar(); if (ch == '-') f = 0;} while (ch > '9' || ch < '0');
	do {x = x * 10 + ch - '0'; ch = getchar();} while (ch >= '0' && ch <= '9');
	x = f ? x : -x;
}

template <typename T> void write (T x) {
	if (x < 0) x = ~x + 1, putchar ('-');
	if (x > 9) write (x / 10);
	putchar (x % 10 + '0');
}

const int N = 2e5 + 7;

struct EDGE {
	int to, nxt, w;
} edge[N << 1];

int n, m, E, ans, col[N], head[N];
char ch[10]; 

inline void addedge(int u, int v, int w) {
	edge[++E].to = v;
	edge[E].w = w;
	edge[E].nxt = head[u];
	head[u] = E;
}

inline int first(multiset< int > &s) {
	return s.size() ? *s.rbegin() : -INF;
}

inline int second(multiset< int > &s) {
	return s.size() > 1 ? *(++s.rbegin()) : -INF;
}

multiset < int > path[N], chain[N];

struct Splay {
	int l, r, w, fa, sum, len, lmx, rmx, ans, ch[2];
} t[N];

#define ls(p) (t[p].l)
#define rs(p) (t[p].r)

inline bool ntroot(int x) {
    return t[t[x].fa].ch[0] == x || t[t[x].fa].ch[1] == x;
}

inline void init() {
	for(int i = 0; i <= n; i++) t[i].lmx = t[i].rmx = t[i].ans = -INF;
}

inline void pushup(int p) {
	t[p].sum = t[ls(p)].sum + t[rs(p)].sum + t[p].len;
	int cha = max(t[p].w, first(chain[p]));
	int L = max(cha, t[ls(p)].rmx + t[p].len);
	int R = max(cha, t[rs(p)].rmx);
	t[p].lmx = max(t[ls(p)].lmx, t[ls(p)].sum + t[p].len + R);
	t[p].rmx = max(t[rs(p)].rmx, t[rs(p)].sum + L);
	t[p].ans = max(t[ls(p)].rmx + t[p].len + R, t[rs(p)].lmx + L);
	t[p].ans = max(t[p].ans, max(t[ls(p)].ans, t[rs(p)].ans));
	t[p].ans = max(t[p].ans, first(path[p]));
	t[p].ans = max(t[p].ans, first(chain[p]) + second(chain[p]));
	if(t[p].w == 0) t[p].ans = max(t[p].ans, max(first(chain[p]), 0));
} 

inline void up(int p) {
	t[p].sum = t[ls(p)].sum + t[rs(p)].sum + t[p].len;
	int xu = max(t[p].w, first(chain[p]));
	t[p].lmx = max(t[ls(p)].lmx, max(t[ls(p)].sum + t[p].len + t[rs(p)].lmx, t[ls(p)].sum + t[p].len + xu));
	t[p].rmx = max(t[rs(p)].rmx, max(t[rs(p)].sum + t[p].len + t[ls(p)].rmx, t[rs(p)].sum + xu));
	t[p].ans = max(t[ls(p)].rmx + t[p].len + max(xu, t[rs(p)].lmx), t[rs(p)].lmx + xu);
	t[p].ans = max(t[p].ans, max(t[ls(p)].ans, t[rs(p)].ans));
	t[p].ans = max(t[p].ans, first(path[p]));
	t[p].ans = max(t[p].ans, first(chain[p]) + second(chain[p]));
	if(t[p].w == 0) t[p].ans = max(t[p].ans, max(first(chain[p]), 0));
}

inline void rotate(int x){
    int y = t[x].fa, z = t[y].fa, k = t[y].ch[1] == x;
    if(ntroot(y)) t[z].ch[t[z].ch[1] == y] = x;
    t[x].fa = z; t[y].ch[k] = t[x].ch[k ^ 1];
    if(t[x].ch[k ^ 1]) t[t[x].ch[k ^ 1]].fa = y;
    t[y].fa = x; t[x].ch[k ^ 1] = y;
    pushup(y); pushup(x);
}

inline void splay(int p) {
    while(ntroot(p)) {
        int f = t[p].fa, g = t[f].fa;
        if(ntroot(f)) rotate((t[f].ch[0] == p) == (t[g].ch[0] == f) ? f : p);
        rotate(p);
    }
    pushup(p);
}

inline void access(int x) {
    for(int y = 0; x; y = x, x = t[x].fa) {
        splay(x);
        if(rs(x)) path[x].insert(t[rs(x)].ans), chain[x].insert(t[rs(x)].lmx);
        if(y) path[x].erase(path[x].find(t[y].ans)), chain[x].erase(chain[x].find(t[y].lmx));
        t[x].ch[1] = y;
        pushup(x);
    }
}

inline void dfs(int u) {
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if(t[u].fa == v) continue;
		t[v].len = edge[i].w; t[v].fa = u; dfs(v);
		path[u].insert(t[v].ans); chain[u].insert(t[v].lmx);
	}
	pushup(u);
}

inline void modify(int x) {
	access(x); splay(x);
	col[x] ^= 1; t[x].w = !col[x] ? 0 : -INF;
	pushup(x); ans = t[x].ans;
}

int main() {
	read(n); init();
	for(int i = 1, u, v, w; i < n; i++) {
		read(u); read(v); read(w);
		addedge(u, v, w);
		addedge(v, u, w);
	}
	dfs(1); ans = t[1].ans; read(m); 
	for(int i = 1, x; i <= m; i++) {
		scanf("%s", ch);
		if(ch[0] == 'A') {
			if(ans < 0) puts("They have disappeared.");
			else printf("%d\n", ans);
		} else {
			read(x);
			modify(x);
		} 
	}
	return 0;
}

2020/8/15 22:56
加载中...