题意：给定一棵树，告诉了每条边的权值，然后给出两种操作：

(1)把第i条边的权值改为val

(2)询问a，b路径上权值最大的边

 

分析：本题与HDU3966差不多，区别就是：HDU3966是告诉树中点权的值，这里是边权。

所以我们可以转化，用边的孩子节点来表示该边。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=50010;const int INF=1<<30;int n,tim;int num[N],siz[N],top[N],son[N];int dep[N],tid[N],rank[N],fa[N];int head[N],to[2*N],next[2*N],w[2*N],edge;struct Edge{    int u,v,c;};Edge tmp[2*N];void Init(){    memset(head,-1,sizeof(head));    memset(son,-1,sizeof(son));    tim=0;    edge=0;}void addedge(int u,int v,int c){    to[edge]=v,w[edge]=c,next[edge]=head[u],head[u]=edge++;    to[edge]=u,w[edge]=c,next[edge]=head[v],head[v]=edge++;}//树链剖分部分void dfs1(int u,int father,int d){    dep[u]=d;    fa[u]=father;    siz[u]=1;    for(int i=head[u]; ~i; i=next[i])    {        int v=to[i];        if(v!=father)        {            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]=++tim;    rank[tid[u]]=u;    if(son[u]==-1) return;    dfs2(son[u],tp);    for(int i=head[u]; ~i; i=next[i])    {        int v=to[i];        if(v!=son[u]&&v!=fa[u])            dfs2(v,v);    }}//线段树部分#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int MAX[4*N];void PushUP(int rt){    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);}void Build(int l,int r,int rt){    if(l==r)    {        MAX[rt]=num[l];        return;    }    int mid=(l+r)>>1;    Build(lson);    Build(rson);    PushUP(rt);}void Update(int l,int r,int rt,int p,int val){    if(l==r)    {        MAX[rt]=val;        return;    }    int mid=(l+r)>>1;    if(p<=mid)        Update(lson,p,val);    else        Update(rson,p,val);    PushUP(rt);}int Query(int l,int r,int rt,int L,int R){    if(L<=l&&R>=r)        return MAX[rt];    int mid=(l+r)>>1;    int ret=-INF;    if(L<=mid) ret=max(ret,Query(lson,L,R));    if(R>mid)  ret=max(ret,Query(rson,L,R));    return ret;}void Change(int x,int val){    if(dep[tmp[x].u]>dep[tmp[x].v])        Update(2,n,1,tid[tmp[x].u],val);    else        Update(2,n,1,tid[tmp[x].v],val);}int query(int x,int y){    int ans=-INF;    while(top[x]!=top[y])    {        if(dep[top[x]]
        
         dep[y]) swap(x,y);    if(x!=y) ans=max(ans,Query(2,n,1,tid[x]+1,tid[y]));    return ans;}int main(){    char oper[15];    int a,b,c,t;    scanf("%d",&t);    while(t--)    {        Init();        scanf("%d",&n);        for(int i=1; i
         
          dep[tmp[i].v]) num[tid[tmp[i].u]]=tmp[i].c; else num[tid[tmp[i].v]]=tmp[i].c; } Build(2,n,1); while(1) { scanf("%s",oper); if(oper[0]=='D') break; scanf("%d%d",&a,&b); if(oper[0]=='Q') printf("%d\n",query(a,b)); else Change(a,b); } } return 0;}