https://vjudge.net/problem/SPOJ-QTREE
題意:
一棵樹,每條邊有個權值
兩種操作
一個修改每條邊權值
一個詢問兩點之間這一條鍊的最大邊權
Example
Input:
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
Output:
1
3
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=210000;
const int inf=0x3fffffff;
int son[N],father[N],sz[N],head[N],num;
int ti[N],idx,dep[N],top[N];
struct edge{
int ed,nxt;
}e[N*3];
struct Edge{
int x,y,v;
}E[N*2];
int max(int a,int b){
if(a>b)return a;
return b;
}
void addedge(int x,int y){
e[++num].ed=y;e[num].nxt=head[x];head[x]=num;
e[++num].ed=x;e[num].nxt=head[y];head[y]=num;
}
void dfs_find(int u,int fa){//處理每棵子樹大小和重兒子
sz[u]=1;dep[u]=dep[fa]+1;son[u]=0;father[u]=fa;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].ed;
if(v==fa)continue;
dfs_find(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v])son[u]=v;
}
}
void dfs_time(int u,int fa){
ti[u]=idx++;
top[u]=fa;
if(son[u]!=0)dfs_time(son[u],top[u]);//處理同重鍊上點的top
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].ed;
if(v==father[u]||v==son[u])continue;//枚舉到了同一重鍊上的點就跳過
dfs_time(e[i].ed,e[i].ed);
}
}
struct tree{
int l,r,v;
}T[N<<2];
void buildtree(int l,int r,int id){
T[id].l=l;T[id].r=r;T[id].v=-inf;
if(l==r)return;
int mid=(l+r)>>1;
buildtree(l,mid,id*2);
buildtree(mid+1,r,id*2+1);
}
void update(int id,int cp,int v){
if(T[id].l==T[id].r){T[id].v=v;return;}
int mid=(T[id].l+T[id].r)>>1;
if(mid>=cp)update(id*2,cp,v);
if(mid<cp)update(id*2+1,cp,v);
T[id].v=max(T[id*2].v,T[id*2+1].v);
}
int query(int l,int r,int id){
if(T[id].r==r&&T[id].l==l)return T[id].v;
int mid=(T[id].l+T[id].r)>>1;
if(mid>=r)return query(l,r,id*2);
else if(mid<l)return query(l,r,id*2+1);
else return max(query(l,mid,id*2),query(mid+1,r,id*2+1));
}
int lca(int x,int y){
int ans=-inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=max(ans,query(ti[top[x]],ti[x],1));
x=father[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)ans=max(ans,query(ti[x]+1,ti[y],1));
return ans;
}
int main(){
int n,t,x,y,v,j;
char str[100];
scanf("%d",&t);
while(t--){
memset(head,0,sizeof(head));
num=0;scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].v);
addedge(E[i].x,E[i].y);
}
dep[1]=0;sz[0]=0;idx=1;
dfs_find(1,1);
dfs_time(1,1);
buildtree(2,n,1);
for(int i=1;i<n;i++){
if(dep[E[i].x]<dep[E[i].y])swap(E[i].x,E[i].y);
update(1,ti[E[i].x],E[i].v);
}
while(true){
scanf("%s",str);
if(str[0]=='D')break;
else if(str[0]=='Q'){
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
else if(str[0]=='C'){
scanf("%d%d",&j,&v);
update(1,ti[E[j].x],v);
}
}
}
return 0;
}