题意：给定一棵树，求一条路径上的边权最大值
思路：树链剖分，把一颗树，转化成一个区间，就可以用线段树，快速解决一些问题了
至此用这个模板终于会处理点权问题了，LCA那个dfs序转成链，我不会算点权的
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define lson(x) 2*x #define rson(x) 2*x+1 const int maxn = 1e4+5; struct Edge { int to,next,cost; }edge[maxn*4]; int e1[maxn],e2[maxn],cost[maxn]; int head[maxn],tot,cnt; int root,size[maxn],dep[maxn],fa[maxn],son[maxn]; int top[maxn],id[maxn],val[maxn]; /* size -> 以x为根节点子树的大小 dep -> 深度 fa -> 父节点 son -> 重儿子 top -> x所在重链的顶端节点 id -> 这个点在线段树中的位置 */ struct data { int l,r,num; }node[maxn*4]; void init() { memset(head,-1,sizeof head); tot = 0; cnt = 0; } void add(int x,int y,int val) { edge[tot].to = y; edge[tot].cost = val; edge[tot].next = head[x]; head[x] = tot++; } int dfs1(int x,int pre,int d) { size[x] = 1; fa[x] = pre; dep[x] = d; son[x] = 0; for(int i = head[x]; i != -1; i = edge[i].next) { int y = edge[i].to; if(y != pre) { size[x] += dfs1(y,x,d+1); if(size[y] > size[son[x]]) son[x] = y; } } return size[x]; } void dfs2(int x,int pre) { id[x] = ++cnt; top[x] = pre; if(son[x]) dfs2(son[x],pre); //重链 for(int i = head[x]; i != -1; i = edge[i].next) { int y = edge[i].to; if(y != fa[x] && y != son[x]) dfs2(y,y); //轻链 } } void pushup(int cnt) { node[cnt].num = max(node[lson(cnt)].num,node[rson(cnt)].num); } void build(int x,int y, int cnt) { node[cnt].l = x; node[cnt].r = y; if(x == y) { node[cnt].num = val[x]; return; } int mid = (x+y) / 2; build(x,mid,lson(cnt)); build(mid+1,y,rson(cnt)); pushup(cnt); } void up(int x,int y,int cnt,int val) { if(x == node[cnt].l && y == node[cnt].r) { node[cnt].num = val; return; } int fa = 2*cnt; if(x <= node[fa].r) { if(y <= node[fa].r) up(x,y,fa,val); else up(x,node[fa].r,fa,val); } fa++; if(y >= node[fa].l) { if(x >= node[fa].l) up(x,y,fa,val); else up(node[fa].l,y,fa,val); } pushup(cnt); } int fid(int x,int y,int cnt) { int res = 0; if(x == node[cnt].l && y == node[cnt].r) { return node[cnt].num; } int fa = 2*cnt; if(x <= node[fa].r) { if(y <= node[fa].r) res = max(res,fid(x,y,fa)); else res = max(res,fid(x,node[fa].r,fa)); } fa++; if(y >= node[fa].l) { if(x >= node[fa].l) res = max(res,fid(x,y,fa)); else res = max(res,fid(node[fa].l,y,fa)); } return res; } int qurey(int u,int v) { int ans = 0; while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u,v); ans = max(ans,fid(id[top[u]],id[u],1)); u = top[u]; u = fa[u]; } if(dep[u] > dep[v]) swap(u,v); ans = max(ans,fid(id[son[u]],id[v],1)); return ans;//存的都是点的父边，最上面的点用son[u] } int main() { int T,n,kase = 1; char ch[50]; scanf("%d",&T); while(T--) { if(kase++ != 1) putchar('\n'); scanf("%d",&n); init(); for(int i = 1; i < n; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e1[i] = a;e2[i] = b;cost[i] = c; add(a,b,c); add(b,a,c); } root = (n+1) / 2; dfs1(root,root,1); dfs2(root,root); for(int i = 1; i < n; i++) { if(dep[ e1[i] ] < dep[ e2[i] ]) swap(e1[i],e2[i]); val[ id[e1[i]] ] = cost[i]; } build(1,cnt,1); while(scanf("%s",ch)!=EOF && ch[0]!='D') { int a,b; scanf("%d%d",&a,&b); if(ch[0] == 'Q') { int ans = qurey(a,b); printf("%d\n",ans); } else up(id[e1[a]],id[e1[a]],1,b); } } }
