首页 > 代码库 > HDU 4010.Query on The Trees 解题报告
HDU 4010.Query on The Trees 解题报告
题意：
给出一颗树，有4种操作：
1、如果x和y不在同一棵树上则在xy连边
2、如果x和y在同一棵树上并且x!=y则把x换为树根并把y和y的父亲分离
3、如果x和y在同一棵树上则x到y的路径上所有的点权值+w
4、如果x和y在同一棵树上则输出x到y路径上的最大值
动态树入门题：
#include <iostream>#include <cstdio>using namespace std;const int MAXN = 333333;struct node { int val, max, inc; bool rev; node *par, *Ch[2];} dt[MAXN], *NIL = dt;struct LinkcutTree { inline void _inc (node * x, int inc) { if (x == NIL) return; x->inc += inc, x->val += inc, x->max += inc; } inline void clear (node *const x) { if (x == NIL) return ; if (x->inc) { _inc (x->Ch[0], x->inc); _inc (x->Ch[1], x->inc); x->inc = 0; } if (x->rev) { swap (x->Ch[0], x->Ch[1]); x->Ch[0]->rev ^= 1; x->Ch[1]->rev ^= 1; x->rev = 0; } } inline void update (node * x) { clear (x); clear (x->Ch[0]), clear (x->Ch[1]); x->max = max (x->val, max (x->Ch[0]->max, x->Ch[1]->max) ); } void Rotate (node *x) { node *p = x->par, *g = p->par; clear (p),clear (x); int c = p->Ch[0] == x; //0左旋，1右旋 p->Ch[c ^ 1] = x->Ch[c]; if (x->Ch[c] != NIL) x->Ch[c]->par = p; x->par = g; if (g->Ch[0] == p) g->Ch[0] = x; else if (g->Ch[1] == p) g->Ch[1] = x; x->Ch[c] = p; p->par = x; update (p); } void Splay (node *x) { if(x==NIL) return ; while (x->par != NIL && (x->par->Ch[0] == x || x->par->Ch[1] == x) ) { if (x->par != NIL) Rotate (x); else { node *p = x->par, *g = p->par; if ( (g->Ch[1] == p) == (p->Ch[1] == x) ) Rotate (p), Rotate (x); else Rotate (x), Rotate (x); } } update (x); } node *Access (node *u) { node *v = NIL; for (; u != NIL; u = u->par) { Splay (u); u->Ch[1] = v; update (v = u); } return v; } node *getroot (node *x) { for (x = Access (x); clear (x), x->Ch[0] != NIL; x = x->Ch[0]); return x; } inline void evert (node *x) { Access (x)->rev ^= 1; Splay (x); } inline void link (node *x, node *y) { evert (x); x->par = y; Access (x); } inline void cut (node *x, node *y) { evert (x); Access (y); Splay (y); y->Ch[0]->par = NIL; y->Ch[0] = NIL; update (y); } inline int query (node *x, node *y) { evert (x); Access (y), Splay (y); return y->max; } inline void modify (node *x, node *y, int w) { evert (x); Access (y), Splay (y); _inc (y, w); }} LCT;int n, m;int main() { while (scanf ("%d", &n) != EOF) { for (int i = 0; i <= n; i++) { dt[i].val = dt[i].max = dt[i].inc = 0; dt[i].par = dt[i].Ch[0] = dt[i].Ch[1] = NIL; dt[i].rev = 0; } for (int i = 1, x, y; i < n; ++i) { scanf ("%d %d", &x, &y); LCT.link (dt + x, dt + y); } for (int i = 1, x; i <= n; ++i) { scanf ("%d", &x); node *tem = dt + i; LCT.Splay (tem); tem->val = tem->max = x; LCT.update (tem); } scanf ("%d", &m); for (int i = 0, op, x, y, z; i < m; ++i) { scanf ("%d%d%d", &op, &x, &y); switch (op) { case 1: if (LCT.getroot (dt + x) == LCT.getroot (dt + y) ) printf ("-1\n"); else LCT.link (dt + x, dt + y); break; case 2: if (x == y || LCT.getroot (dt + x) != LCT.getroot (dt + y) ) printf ("-1\n"); else LCT.cut (dt + x, dt + y); break; case 3: scanf ("%d", &z); if (LCT.getroot (dt + y) != LCT.getroot (dt + z) ) printf ("-1\n"); else LCT.modify (dt + y, dt + z, x); break; case 4: if (LCT.getroot (dt + x) != LCT.getroot (dt + y) ) printf ("-1\n"); else printf ("%d\n", LCT.query (dt + x, dt + y) ); break; } } putchar (10); }}
HDU 4010.Query on The Trees 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。