SPOJ QTREE Query on a Tree

题目

题目传送门

题目大意

给定一棵节点数为NN<script type="math/tex" id="MathJax-Element-1">N</script>的树，有两种操作：CHANGE i ti,QUERY a b，分别表示将编号为i的边的权值改为ti，查询由节点a到节点b路径中的最大值。对于每一个QUERY操作，输出节点a到节点b路径中的最大值。

思路

树链剖分板子题。

我们使用线段树来维护最大权值，则这道题树链剖分后就变成了线段树单点修改+区间查询问题。

实现细节

由于权值在边上，故我们可以将权值下放到点，并将根节点权值设为-INF。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define lch rt<<1
#define rch rt<<1|1const int Maxn=50000;
const int INF=0x3fffffff;int N,dcnt;
int val[Maxn+5],siz[Maxn+5],top[Maxn+5],son[Maxn+5];
int dep[Maxn+5],tid[Maxn+5],rnk[Maxn+5],fa[Maxn+5];
int belong[Maxn+5];struct Tnode {int v,w,id;Tnode *nxt;
}Edge[Maxn*2+5];
Tnode *G[Maxn+5],*ecnt;struct Snode {int maxs;
}Seg[Maxn*4+5];void Init() {memset(G,0,sizeof G);memset(son,-1,sizeof son);dcnt=0;ecnt=&Edge[0];
}void AddEdge(int u,int v,int w,int id) {Tnode *p=++ecnt;p->v=v,p->w=w,p->id=id;p->nxt=G[u],G[u]=p;p=++ecnt;p->v=u,p->w=w,p->id=id;p->nxt=G[v],G[v]=p;
}void DFS1(int u,int f,int d) {dep[u]=d,fa[u]=f,siz[u]=1;for(Tnode *p=G[u];p!=NULL;p=p->nxt) {int v=p->v,id=p->id;if(v==f)continue;belong[id]=v;val[v]=p->w;DFS1(v,u,d+1);siz[u]+=siz[v];if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;}
}void DFS2(int u,int tp) {top[u]=tp,tid[u]=++dcnt,rnk[dcnt]=u;if(son[u]==-1)return;DFS2(son[u],tp);for(Tnode *p=G[u];p!=NULL;p=p->nxt) {int v=p->v;if(v==son[u]||v==fa[u])continue;DFS2(v,v);}
}void PushUp(int rt) {Seg[rt].maxs=max(Seg[lch].maxs,Seg[rch].maxs);
}void Build(int rt,int l,int r) {if(l==r) {Seg[rt].maxs=val[rnk[l]];return;}int mid=(l+r)>>1;Build(lch,l,mid);Build(rch,mid+1,r);PushUp(rt);
}void Update(int rt,int l,int r,int pos,int val) {if(l==r) {Seg[rt].maxs=val;return;}int mid=(l+r)>>1;if(pos<=mid)Update(lch,l,mid,pos,val);else Update(rch,mid+1,r,pos,val);PushUp(rt);
}int Query(int rt,int l,int r,int st,int ed) {if(st<=l&&r<=ed)return Seg[rt].maxs;int mid=(l+r)>>1,ret=-INF;if(st<=mid)ret=max(ret,Query(lch,l,mid,st,ed));if(ed>mid)ret=max(ret,Query(rch,mid+1,r,st,ed));return ret;
}void Change(int i,int val) {int u=belong[i];Update(1,2,N,tid[u],val);
}int Ask(int u,int v) {int ans=-INF;while(top[u]!=top[v]) {if(dep[top[u]]<dep[top[v]])swap(u,v);ans=max(ans,Query(1,2,N,tid[top[u]],tid[u]));u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);if(u!=v)ans=max(ans,Query(1,2,N,tid[u]+1,tid[v]));return ans;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifchar op[20];int u,v,w,cas;scanf("%d",&cas);while(cas--) {Init();scanf("%d",&N);for(int i=1;i<N;i++) {scanf("%d %d %d",&u,&v,&w);AddEdge(u,v,w,i);}DFS1(1,1,1);DFS2(1,1);Build(1,2,N);while(true) {scanf("%s",op);if(op[0]=='D')break;scanf("%d %d",&u,&v);if(op[0]=='Q')printf("%d\n",Ask(u,v));else Change(u,v);}}return 0;
}