题目链接：点击打开链接
把边权化成点权，，每个点的点权表示父边的边权。
求path(x, y)
把x access后，则 x 就变成了根所在的splay ， 且x是这条链上深度最大的节点。(下面对于根所在的splay称为splay_root)
那么y沿着父节点爬上去，当父节点 fa_y 坐落在splay_root上时，fa_y深度一定比x小，即一定在x的上方。
再把y access上去, 在y最后要和splay_root合并之前， 把fa_y splay一下，
那么path(x, y) 的一部分就是 fa_y ->x : fa_y->splay(), return paht(fa_y, x) => fa_y->ch[1]->max
另一部分为 y一直access上来的那条链， splay->max
#include <iostream>#include <fstream>#include <string>#include <time.h>#include <vector>#include <map>#include <queue>#include <algorithm>#include <stack>#include <cstring>#include <cmath>#include <set>#include <vector>using namespace std;template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}typedef long long ll;typedef pair<int, int> pii;const int N = 30005;const int inf = 10000000;struct Node *null;struct Node{Node *fa, *ch[2];int size;int val, ma, sum, id;bool rev;inline void put(){printf("%d:id, %d,%d,%d (%d,%d) fa:%d \n", id, val, ma, sum, ch[0]->id, ch[1]->id, fa->id);}void debug(Node *x){if (x == null)return;x->put();if (x->ch[0] != null)putchar('L'), debug(x->ch[0]);if (x->ch[1] != null)putchar('r'), debug(x->ch[1]);}inline void clear(int _val, int _id){fa = ch[0] = ch[1] = null;size = 1;rev = 0;id = _id;val = ma = sum = _val;}inline void add_val(int _val){val += _val;sum += _val;ma = max(ma, val);}inline void push_up(){size = 1 + ch[0]->size + ch[1]->size;sum = ma = val;if (ch[0] != null) {sum += ch[0]->sum; ma = max(ma, ch[0]->ma);}if (ch[1] != null){sum += ch[1]->sum;ma = max(ma, ch[1]->ma);}}inline void push_down(){if (rev){flip(); ch[0]->rev ^= 1; ch[1]->rev ^= 1;}}inline void setc(Node *p, int d){ch[d] = p;p->fa = this;}inline bool d(){return fa->ch[1] == this;}inline bool isroot(){return fa == null || fa->ch[0] != this && fa->ch[1] != this;}inline void flip(){if (this == null)return;swap(ch[0], ch[1]);rev ^= 1;}inline void go(){//从链头开始更新到thisif (!isroot())fa->go();push_down();}inline void rot(){Node *f = fa, *ff = fa->fa;int c = d(), cc = fa->d();f->setc(ch[!c], c);this->setc(f, !c);if (ff->ch[cc] == f)ff->setc(this, cc);else this->fa = ff;f->push_up();}inline Node*splay(){go();while (!isroot()){if (!fa->isroot())d() == fa->d() ? fa->rot() : rot();rot();}push_up();return this;}inline Node* access(){//access后this就是到根的一条splay，并且this已经是这个splay的根了for (Node *p = this, *q = null; p != null; q = p, p = p->fa){p->splay()->setc(q, 1);p->push_up();}return splay();}inline Node* find_root(){Node *x;for (x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]);return x;}void make_root(){access()->flip();}void cut(){//把这个点的子树脱离出去access();ch[0]->fa = null;ch[0] = null;push_up();}void cut(Node *x){if (this == x || find_root() != x->find_root())return;else {x->make_root();cut();}}void link(Node *x){if (find_root() == x->find_root())return;else {make_root(); fa = x;}}};Node pool[N], *tail;Node *node[N], *ee[N];int n, q;void debug(Node *x){if (x == null)return;x->put();debug(x->ch[0]);debug(x->ch[1]);}inline int ask(Node *x, Node *y){x->access();for (x = null; y != null; x = y, y = y->fa){y->splay();if (y->fa == null)return max(y->ch[1]->ma, x->ma);y->setc(x, 1);y->push_up();}}struct Edge{int from, to, dis, id, nex;}edge[N << 1];int head[N], edgenum;void add(int u, int v, int dis, int id){Edge E = { u, v, dis, id, head[u] };edge[edgenum] = E;head[u] = edgenum++;}bool vis[N];void bfs(){fill(vis + 1, vis + 1 + n, false);queue<int>q;q.push(1);vis[1] = true;while (!q.empty()){int u = q.front(); q.pop();for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to;if (vis[v])continue;vis[v] = true;q.push(v);ee[edge[i].id] = node[v];node[v]->val = edge[i].dis;node[v]->push_up();node[v]->fa = node[u];}}}int main(){int T; rd(T);while (T–){rd(n);fill(head + 1, head + n + 1, -1); edgenum = 0;tail = pool;null = tail++;null->clear(-inf, 0);null->size = 0;for (int i = 1; i <= n; i++) {node[i] = tail++;node[i]->clear(0, i);}for (int i = 1, u, v, d; i < n; i++){rd(u); rd(v); rd(d);add(u, v, d, i);add(v, u, d, i);}bfs();char str[10]; int u, v;while (true){scanf("%s", str);if (str[0] == 'D')break;rd(u); rd(v);if (str[0] == 'Q')pt(ask(node[u], node[v])), putchar('\n');else {ee[u]->splay()->val = v;ee[u]->push_up();}}}return 0;}/**/
版权声明：本文为博主原创文章，未经博主允许不得转载。
旅行要学会随遇而安，淡然一点，走走停停，
