记录编号	413279	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.251 s
提交时间	2017-06-11 10:54:11	内存使用	8.33 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
inline int read(){
  int s=0,f=1; char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
  return s*f;       
}
int r[100005],tot,n;
struct oo{
  int fr,to,next,vv;       
}c[100005*2];
inline void add(int x,int y,int z){
  c[tot].fr=x;
  c[tot].to=y;
  c[tot].vv=z;
  c[tot].next=r[x];
  r[x]=tot++;     
}
int deep[100001],size[100001],son[100001],v[100001],fa[100001];
inline void dfs1(int x){
  size[x]=1; son[x]=0;
  for(int i=r[x];i!=-1;i=c[i].next){
    if(c[i].to!=fa[x]){
     fa[c[i].to]=x;
     v[c[i].to]=c[i].vv;
     deep[c[i].to]=deep[x]+1;
     dfs1(c[i].to);
     size[x]+=size[c[i].to];
     if(size[son[x]]<size[c[i].to]) 
      son[x]=c[i].to;                   
    }        
  }       
}
int top[100001],cnt,pos[100001],fir[100001],tree[400004];
inline void dfs2(int u,int v){
  top[u]=v;
  fir[u]=++cnt;
  pos[cnt]=u;
  if(son[u]) dfs2(son[u],v);
  for(int i=r[u];i!=-1;i=c[i].next)
   if(c[i].to!=fa[u]&&c[i].to!=son[u])        
    dfs2(c[i].to,c[i].to);
}
inline void build(int root,int l,int r){
   if(l==r){
    tree[root]=v[pos[l]] ;
    return ;        
   }      
   int mid=(l+r)>>1;
   build(lson); build(rson);
   tree[root]=max(tree[root<<1],tree[root<<1|1]);
}
inline int query(int L,int R,int root,int l,int r){
  if(L<=l&&R>=r) return tree[root];
  int mid=(l+r)>>1,ans=-0xffffff;
  if(L<=mid) ans=max(ans,query(L,R,lson));
  if(R>mid) ans=max(ans,query(L,R,rson));
  return ans;
}
 inline int ques(int x,int y){    
  int fx=top[x],fy=top[y],ans=-0xffffff;
  while(fx!=fy){ //  SSSS
    if(deep[fx]<deep[fy]){
     swap(x,y);
     swap(fx,fy);                      
    }
    ans=max(ans,query(fir[fx],fir[x],1,1,n)); 
    x=fa[fx]; fx=top[x];                                   
  }       
  if(deep[x]>deep[y]) swap(x,y);
  if(fir[x]<fir[y])
   ans=max(ans,query(fir[x]+1,fir[y],1,1,n));
  return ans;
}
inline void change(int pos,int to,int root,int l,int r){
 if(l==r){
  tree[root]=to;
  return ;         
 }       
 int mid=(l+r)>>1;
 if(pos<=mid) change(pos,to,lson);
 else change(pos,to,rson);
 tree[root]=max(tree[root<<1],tree[root<<1|1]);
}
int main(){
  freopen("qtree.in","r",stdin);
  freopen("qtree.out","w",stdout);
  n=read();
  for(int i=0;i<=n;i++) r[i]=-1;
  for(int i=1;i<n;i++){
   int x=read(),y=read(),z=read();
   add(x,y,z); add(y,x,z);
  }
  dfs1(1); dfs2(1,1); build(1,1,n);
  char ll[15];
  while(~scanf("%s",ll)&&ll[0]!='D'){
   if(ll[0]=='Q')
    printf("%d\n",ques(read(),read()));
   else{
    int x=read(),y=read();
    int pp=(x<<1)-1;
    if(fa[c[pp].fr]==c[pp].to)
     change(fir[c[pp].fr],y,1,1,n); 
    else
     change(fir[c[pp].to],y,1,1,n);  
   }                               
  }
  //while(1);
}