之前做了两道点权的LCT,这次做一下边权的LCT.上网找了一下资料，发现对于边权的LCT有这么两种处理方法，一种是每条边建一个点，于是边权就转成点权了。另外一种则是每个边权对应到点权上，也就是每个点对应它的父边，这就要求树不能换根，不换根提路径是有点蛋疼的，所以就需要知道怎么在不换根的时候提取出u到 v的路径，实现的方法是基于expose的一种lca。
传统的expose是一直expose到根，另一种做法则是，对于u,v，expose(v),splay(v),这样v到父亲的边打成了重链，然后相应的执行一种类似于expose(u)的操作，但是中止条件改为当u->fa==null的时候就应该结束while,因为u->fa==null说明u和v在同一条重链上，或者说此时u就是lca(u,v)，利用lca函数（传指针的引用），最后v和u->ch[1]就是lca到u,v的两个方向的路径。具体可以对比一下expose和lca函数
另外一点是我在debug的时候学习到的，原来的模板里的expose是没有由下往上更新的，也就是说expose(v)之后，v上的所有祖先的信息都是没有更新的，因此expose之后还要splay(v)，将信息往上带，但是由于lca函数传的是引用，调用完之后原本的信息就丢失掉了，所以可以在循环里直接upd，把正确的信息往上传。
时间4600ms，差点超时，做这题其实也只是为了学习如何用LCT来操作边权。
#pragma warning(disable:4996)#include#include #include #include #include #include #include using namespace std;#define ll long long#define maxn 12000#define NINF -1000000000struct Edge{ int u, v, w; Edge(int ui, int vi, int wi) :u(ui), v(vi), w(wi){} Edge(){}}E[maxn * 2], etop;struct Node{ Node *p, *ch[2]; int val; int mx; int size; bool isRoot; Node *fa; Node(){ val = NINF; size = 0; isRoot = false; mx = NINF; } void setc(Node *c, int d){ ch[d] = c; c->p = this; } bool d(){ return p->ch[1] == this; } void upd(){ mx = max(val, max(ch[0]->mx, ch[1]->mx)); } void relax(); void setRoot(Node *f);}Tnull, *null = &Tnull;void Node::relax(){}void Node::setRoot(Node *f){ isRoot = true; fa = f; p = null;}Node mem[maxn], *C = mem;Node *make(int v){ C->val = C->mx = v; C->ch[0] = C->ch[1] = null; C->isRoot = true; C->p = null; C->fa = null; return C++;}void rot(Node *t){ Node *p = t->p; p->relax(); t->relax(); bool d = t->d(); p->p->setc(t, p->d()); p->setc(t->ch[!d], d); t->setc(p, !d); p->upd(); if (p->isRoot){ p->isRoot = false; t->isRoot = true; t->fa = p->fa; }}void pushTo(){}void splay(Node *u, Node *f = null){ pushTo(); while (u->p != f){ if (u->p->p == f) rot(u); else u->d() == u->p->d() ? (rot(u->p), rot(u)) : (rot(u), rot(u)); } u->upd();}Node *v[maxn];vector G[maxn];vector W[maxn];int n; int nQ;int que[maxn], fa[maxn], qh = 0, qt = 0;int dep[maxn];int wht[maxn];void bfs(){ qh = qt = 0; que[qt++] = 1; fa[1] = -1; while (qh < qt){ int u = que[qh++]; for (int i = 0; i < G[u].size(); i++){ int e = G[u][i]; if (e != fa[u]){ fa[e] = u; v[e]->fa = v[u]; que[qt++] = e; } } }}Node *expose(Node *u){ Node *v; for (v = null; u != null; v = u, u = u->fa){ splay(u); u->ch[1]->setRoot(u); u->setc(v, 1); } return v;}void dfs(int u, int fa){ for (int i = 0; i < G[u].size(); i++){ int v = G[u][i], w = W[u][i]; if (v == fa) continue; dep[v] = dep[u] + 1; wht[v] = w; dfs(v, u); }}void lca(Node *&u, Node *&v){ expose(v); splay(v); for (v = null; u != null; v = u, u = u->fa){ splay(u); if (u->fa == null) return; u->ch[1]->setRoot(u); u->setc(v, 1); u->upd(); }}int main(){ int T; cin >> T; while (T--) { scanf("%d", &n); memset(dep, 0, sizeof(dep)); for (int i = 0; i <= n; i++) G[i].clear(), W[i].clear(); for (int i = 0; i < n - 1; i++){ scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w); G[E[i].u].push_back(E[i].v); G[E[i].v].push_back(E[i].u); W[E[i].u].push_back(E[i].w); W[E[i].v].push_back(E[i].w); } dep[1] = 1; dfs(1, -1); wht[1] = NINF; C = mem; for (int i = 1; i <= n; i++){ v[i] = make(wht[i]); } bfs(); char cmd[10]; int ai, bi; while (scanf("%s", cmd)){ if (cmd[0] == 'D') break; scanf("%d%d", &ai, &bi); if (cmd[0] == 'Q'){ Node *ui = v[ai], *vi = v[bi]; lca(ui, vi); printf("%d\n", max(ui->ch[1]->mx, vi->mx)); } else{ --ai; int ui = E[ai].u, vi = E[ai].v; if (dep[ui] < dep[vi]) swap(ui, vi); Node *u = v[ui]; expose(u); splay(u); u->val = bi; splay(u); } } } return 0;}