树剖一好题。我心水了ww
题目描述
给定一棵n个节点的树，有两个操作：
CHANGE i ti 把第i条边的边权变成ti
QUERY a b 输出从a到b的路径中最大的边权，当a=b的时候，输出0
输入输出格式
输入格式：
第一行输入一个n，表示节点个数
第二行到第n行每行输入三个数，ui，vi，wi，分别表示 ui，vi有一条边，边权是wi
第n+1行开始，一共有不定数量行，每一行分别有以下三种可能
CHANGE，QUERY同题意所述
DONE表示输入结束
输出格式：
对于每个QUERY操作，输出一个数，表示a b之间边权最大值
树链剖分维护。若对应的一组父亲节点(x)与子节点(y)之间有一条边，则将边权存为(y)点的点权。在dfs2内特殊处理即可。
对于修改，线段树动态维护一下最大值。
查询路径最大值按照常规树剖的跳链写法就可以了。由于是边权存为点权，不能计算最近公共祖先。(LCA)所代表的那条边并不在路径上qwq
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 102333
using namespace std;
int h[MAXN],tot=0,cnt=0;
int n,m;
struct qwq
{
int nex,to,w;
int id;
}e[MAXN<<1];
int ans[MAXN<<2];
int w1[MAXN];
int dep[MAXN],son[MAXN]={},fa[MAXN],top[MAXN],siz[MAXN],id[MAXN];
inline void add(int x,int y,int w,int i)
{
e[++tot].to=y;
e[tot].nex=h[x];
e[tot].w=w;
e[tot].id=i;
h[x]=tot;
}
#define leftson cur<<1
#define rightson cur<<1|1
#define mid ((l+r)>>1)
#define push_up ans[cur]=max(ans[leftson],ans[rightson])
inline void build(int cur,int l,int r)
{
if (l==r)
{
ans[cur]=w1[l];
return;
}
build(leftson,l,mid);
build(rightson,mid+1,r);
push_up;
}
int tag[MAXN<<2];
#define push_down lazyadd(leftson,tag[cur]); lazyadd(rightson,tag[cur]); tag[cur]=0
inline void lazyadd(int cur,int del)
{
if (!del) return;
ans[cur]+=del;
tag[cur]+=del;
}
void change(int adl,int adr,int cur,int l,int r,int del)
{
if (adl<=l&&r<=adr)
{
ans[cur]=del;
tag[cur]=del;
return;
}
push_down;
if (adl<=mid) change(adl,adr,leftson,l,mid,del);
if (adl>mid) change(adl,adr,rightson,mid+1,r,del);
push_up;
}
int query(int ql,int qr,int cur,int l,int r)
{
if (ql<=l&&r<=qr)
{
return ans[cur];
}
int answ=-23333;
push_down;
if (ql<=mid) answ=max(answ,query(ql,qr,leftson,l,mid));
if (qr>mid) answ=max(answ,query(ql,qr,rightson,mid+1,r));
return answ;
}
int segid[MAXN];
void dfs_fir(int x,int f,int dept)
{
fa[x]=f;
dep[x]=dept;
siz[x]=1;
int maxn=-1;
for (int i=h[x],y;i;i=e[i].nex)
{
y=e[i].to;
if (y==f) continue;
dfs_fir(y,x,dept+1);
siz[x]+=siz[y];
if (siz[y]>maxn)
{
son[x]=y;
maxn=siz[y];
}
}
}
void dfs_sec(int x,int ft,int w)
{
top[x]=ft;
id[x]=++cnt;
w1[cnt]=w;
if (!son[x]) return;
dfs_sec(son[x],ft,0);
for (int i=h[x],y;i;i=e[i].nex)
{
y=e[i].to;
if (y==fa[x]) continue;
if (y==son[x])
{
w1[id[son[x]]]=e[i].w;
segid[e[i].id]=id[son[x]];
continue;
}
dfs_sec(y,y,e[i].w);
segid[e[i].id]=id[y];
}
}
inline int query_(int x,int y)
{
int answer=-23333;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
answer=max(answer,query(id[top[x]],id[x],1,1,n));
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
answer=max(answer,query(id[x]+1,id[y],1,1,n));
return answer;
}
int main()
{
scanf("%d",&n);
int x,y,w;
for (int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w,i);
add(y,x,w,i);
}
dfs_fir(1,1,1);
dfs_sec(1,1,0);
build(1,1,n);
string s="QWQ";
// for (int i=1;i<=n;i++)
// {
// printf("%d ",w1[id[i]]);
// }
// printf("
");
while (s[0]!='D')
{
cin>>s;
if (s[0]=='D') continue;
scanf("%d%d",&x,&y);
if (s[0]=='Q')
{
if (x==y)
{
printf("0
");
continue;
}
printf("%d
",query_(x,y));
continue;
}
change(segid[x],segid[x],1,1,n,y);
}
return 0;
}