https://www.cnblogs.com/violet-acmer/p/9711441.html
题意：
You are given a tree (an acyclic undirected connected graph,无向无环连通图) with N nodes,
and edges numbered 1, 2, 3...N-1.
We will ask you to perform some instructions of the following form:
有两个操作
CHANGE i ti : change the cost of the i-th edge to ti（第i条边的权值变为ti）
or
QUERY a b : ask for the maximum edge cost on the path from node a to node b
（查询节点a,b间路径的最大权值）
题解：
树链剖分模板题，看代码理解的更快；
AC代码献上：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1 | 1)
const int maxn=; //===========链式前向星===============
struct Node1
{
int to;
int next;
}edge[*maxn];
int head[maxn];
int cnt;
void addEdge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
//====================================
//=========树链剖分用到的变量=========
int fa[maxn];//fa[u] : 节点u的父节点
int newId[maxn];//newId[u] : u与其父亲节点的连边在线段树中的位置
int depth[maxn];//depth[u] : 节点u的深度
int siz[maxn];//siz[u] : 以u为根的子树的节点数
int top[maxn];//top[u] : 节点u所在的重链的顶端节点
int son[maxn];//son[u] : 节点u重儿子
int label;//记录newId[]中新边对应的编号
//====================================
//==========两次DFS()================
void dfs1(int u,int f,int d) //第一遍dfs求出fa[],depth[],siz[],son[]
{
depth[u]=d;
fa[u]=f;
siz[u]=;
for(int i=head[u];~i;i=edge[i].next)
{
int to=edge[i].to;
if(to != f)
{
dfs1(to,u,d+);
siz[u] += siz[to];
if(son[u] == - || siz[to] > siz[son[u]])
son[u] = to;
}
}
}
void dfs2(int u,int sp) //第二遍dfs求出top[]和newId[]
{
top[u]=sp;
newId[u]=++label;
if(son[u] == -)
return ;
dfs2(son[u],sp); for(int i=head[u];~i;i=edge[i].next)
{
int to=edge[i].to;
if(to != son[u] && to != fa[u])
dfs2(to,to);
}
}
//===================================
//=============线段树================
struct Node2
{
int l,r;
int Max;
int mid()
{
return l+((r-l)>>);
}
}segTree[maxn*];
void buildTree(int l,int r,int pos)
{
segTree[pos].l = l,segTree[pos].r = r;
segTree[pos].Max = ;
if(l == r)
return; int mid = (l+r)/;
buildTree(l,mid,ls(pos));
buildTree(mid+,r,rs(pos));
}
void push_up(int k)//向上更新
{
segTree[k].Max = max(segTree[ls(k)].Max,segTree[rs(k)].Max);
}
void update(int k,int val,int pos) //单点更新
{
if(segTree[pos].l == segTree[pos].r)
{
segTree[pos].Max = val;
return;
} int mid=segTree[pos].mid(); if(k <= mid)
update(k,val,ls(pos));
else
update(k,val,rs(pos));
push_up(pos);
}
int query(int l,int r,int pos)//查询线段树中[l,r]的最大值
{
if(segTree[pos].l == l && segTree[pos].r == r)
return segTree[pos].Max; int mid=segTree[pos].mid(); if(r <= mid)
return query(l,r,ls(pos));
else if(l > mid)
return query(l,r,rs(pos));
else
return max(query(l,mid,ls(pos)),query(mid+,r,rs(pos)));
}
int Find(int u,int v)//查询u->v边的最大值
{
int res=;
while(top[u] != top[v])
{
if(depth[top[u]] > depth[top[v]])
{
res=max(res,query(newId[top[u]],newId[u],));
u=fa[top[u]];
}
else
{
res=max(res,query(newId[top[v]],newId[v],));
v=fa[top[v]];
}
}
if(u == v)
return res;
if(depth[u] > depth[v])
swap(u,v);
return max(res,query(newId[son[u]],newId[v],));
}
//===================================
void Init()
{
cnt=;
memset(head,-,sizeof(head));
label=;
memset(son,-,sizeof(son));
}
int e[maxn][];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
Init();
scanf("%d",&n);
for(int i=;i < n;++i)
{
scanf("%d%d%d",&e[i][],&e[i][],&e[i][]);
addEdge(e[i][],e[i][]);
addEdge(e[i][],e[i][]);
}
dfs1(,,);
dfs2(,);
buildTree(,label,);
for(int i=;i < n;++i)
{
if(depth[e[i][]] > depth[e[i][]])
swap(e[i][],e[i][]);//确保 e[i][0] 为 e[i][1]的父节点
update(newId[e[i][]],e[i][],);//更新e[i][1]与其父节点e[i][0]的连边在线段树中的位置
}
char op[];
while(scanf("%s",op) && op[] != 'D')
{
int u,v;
scanf("%d%d",&u,&v);
if(op[] == 'Q')
printf("%d\n",Find(u,v));
else
update(newId[e[u][]],v,);
}
}
}
分割线：2019.5.10
省赛倒计时2天；
熟悉一下树链剖分，改改代码风格：
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e4+; int n;///n个节点
int e[maxn][];///节点e[i][0]与节点e[i][1]有条权值为e[i][2]的边
int num;
int head[maxn];
struct Edge
{
int to;
int next;
}G[maxn<<];
void addEdge(int u,int v)
{
G[num]=Edge{v,head[u]};
head[u]=num++;
}
int fa[maxn];///fa[u]:节点u的父节点
int tid[maxn];///tid[u]:节点u在线段树中的新编号
int rid[maxn];///tid[u]=cnt,rid[cnt]=u,通过线段树中的编号查找节点
int dep[maxn];///节点的深度
int siz[maxn];///siz[u]:以u为根的子树的节点数
int son[maxn];///son[u]:节点u重儿子
int top[maxn];///top[u]:节点u所在重链的顶端节点
struct Seg
{
int l,r;
int maxVal;///区间维护最大值，根据题意而定
int mid(){return l+((r-l)>>);}
int len(){return r-l+;}
}seg[maxn<<];
void pushUp(int pos)
{
seg[pos].maxVal=max(seg[ls(pos)].maxVal,seg[rs(pos)].maxVal);
}
void buildSegTree(int l,int r,int pos)
{
seg[pos].l=l;
seg[pos].r=r;
seg[pos].maxVal=;
if(l == r)
return ;
int mid=l+((r-l)>>);
buildSegTree(l,mid,ls(pos));
buildSegTree(mid+,r,rs(pos));
}
void Update(int l,int val,int pos)///单点更新
{
if(seg[pos].l == seg[pos].r)
{
seg[pos].maxVal=val;
return ;
}
int mid=seg[pos].mid();
if(l <= mid)
Update(l,val,ls(pos));
else
Update(l,val,rs(pos));
pushUp(pos);
}
int Query(int l,int r,int pos)///区间查询
{
if(seg[pos].l == l && seg[pos].r == r)
return seg[pos].maxVal;
int mid=seg[pos].mid();
if(r <= mid)
return Query(l,r,ls(pos));
else if(l > mid)
return Query(l,r,rs(pos));
else
return max(Query(l,mid,ls(pos)),Query(mid+,r,rs(pos)));
}
int Find(int u,int v)
{
int topU=top[u];
int topV=top[v];
int ans=;
while(topU != topV)///u,v不在一条重链上
{
if(dep[topU] > dep[topV])///人为规定topU的深度低
{
swap(topU,topV);
swap(u,v);
}
ans=max(ans,Query(tid[topV],tid[v],));
v=fa[topV];///v来到topV的父节点所在的重链
topV=top[v];
}
if(u == v)
return ans; if(dep[u] > dep[v])
swap(u,v);
return max(ans,Query(tid[son[u]],tid[v],));
}
void DFS1(int u,int f,int depth)///第一遍DFS求出fa,dep,siz,son
{
fa[u]=f;
siz[u]=;
dep[u]=depth;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(v == f)///此处是v == f才continue，在这儿出过错
continue;
DFS1(v,u,depth+);
siz[u] += siz[v];
if(son[u] == - || siz[v] > siz[son[u]])///更新重儿子
son[u]=v;
}
}
void DFS2(int u,int anc,int &k)///第二遍DFS求出tid,rid,top
{
top[u]=anc;
tid[u]=++k;
rid[k]=u;
if(son[u] == -)
return ;
DFS2(son[u],anc,k); for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(v != son[u] && v != fa[u])
DFS2(v,v,k);
}
}
void Solve()
{
DFS1(,,);
int k=;
DFS2(,,k);
buildSegTree(,k,);///[1,k]重新编号的节点建树 for(int i=;i < n;++i)
{
///将e[i][0]与e[i][1]的边权存入儿子节点e[i][1]中
if(dep[e[i][]] > dep[e[i][]])
swap(e[i][],e[i][]);
///更新e[i][1]与其父节点e[i][0]的连边在线段树中的位置
Update(tid[e[i][]],e[i][],);
}
char order[];
while(~scanf("%s",order) && order[] != 'D')
{
int u,v;
scanf("%d%d",&u,&v);
if(order[] == 'Q')
printf("%d\n",Find(u,v));///查询节点u,v间路径的最大值
else///更新第u条边的权值，变为v，第u条边的权值信息记录在了tid[e[u][1]]中
Update(tid[e[u][]],v,);
}
} void Init()///初始化head,num,son
{
num=;
mem(head,-);
mem(son,-);
}
int main()
{
int test;
while(~scanf("%d",&test))
{
while(test--)
{
Init();///多组输入test,Init()放在while(test--)内
scanf("%d",&n);
for(int i=;i < n;++i)///n-1条边
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i][]=u;
e[i][]=v;
e[i][]=w;
addEdge(u,v);
addEdge(v,u);
}
Solve();
}
}
return ;
}