[SCOI2018] Tree [LCT]

[SCOI2018] Tree [LCT]

​​传送门​​

类似 QTREE 的套路, 我们维护到Splay最浅点的最长路径Lmax, 最深点的最长路径Rmax

son 是虚子树, 用一个 multiset 维护虚子树

#include#define N 200050using namespace std;typedef long long ll;const ll inf = 100000000000000;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}int n, m, first[N], nxt[N], to[N], tot;void add(int x, int y){nxt[++tot] = first[x], first[x]=tot, to[tot] = y;}ll val[N], sum[N], Lmax[N], Rmax[N]; int ch[N][2], fa[N];multiset S[N];#define ls ch[x][0]#define rs ch[x][1]bool isRoot(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x;} ll Top(int x){ if(!S[x].empty()) return *S[x].rbegin(); return - inf;}void Pushup(int x){ if(!x) return; sum[x] = sum[ls] + sum[rs] + val[x]; Lmax[x] = max(Lmax[ls], sum[ls] + max(val[x], (max(Lmax[rs], Top(x)) + val[x]))); Rmax[x] = max(Rmax[rs], sum[rs] + max(val[x], (max(Rmax[ls], Top(x)) + val[x])));}void rotate(int x){ int y = fa[x], z = fa[y], k = ch[y][1] == x; if(!isRoot(y)) ch[z][ch[z][1] == y] = x; fa[x] = z; ch[y][k] = ch[x][k^1]; fa[ch[x][k^1]] = y; ch[x][k^1] = y; fa[y] = x; Pushup(y); Pushup(x);}void Splay(int x){ while(!isRoot(x)){ int y = fa[x], z = fa[y]; if(!isRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y); rotate(x); } Pushup(x);}void Access(int x){ for(int y = 0; x; y = x, x = fa[x]){ Splay(x); if(rs) S[x].insert(Lmax[rs]); rs = y; if(rs) S[x].erase(Lmax[rs]); Pushup(x); }}int main(){ n = read(), m = read(); Lmax[0] = Rmax[0] = - inf; for(int i=2; i<=n; i++) fa[i] = read(); for(int i=1; i<=n; i++) val[i] = read(); for(int i=n; i>=1; i--) Pushup(i), S[fa[i]].insert(Lmax[i]); while(m--){ int op = read(); if(op == 1){ int x = read(); Access(x); Splay(x); printf("%lld\n", Rmax[x]); } if(op == 2){ int x = read(), v = read(); Access(x); Splay(x); val[x] = v; Pushup(x); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。