记录编号	119062	评测结果	AAAAAAAAAW
题目名称	[SPOJ 375] 难存的情缘	最终得分	90
用户昵称	HouJikan	是否通过	未通过
代码语言	C++	运行时间	0.313 s
提交时间	2014-09-10 21:51:01	内存使用	0.92 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct edges
{
  int s,e,t;
  int no;
  edges (int s,int e,int t,int no):s(s),e(e),t(t),no(no){};
};
//==============var declaration=================
#define y1 y
int minv[10000*3],maxv[10000*3],son[10001],top[10001],siz[10001],dep[10001], fa[10001],w[10001];
bool vis[10001];
bool negated[10000*3];
int t,n,y1,y2,totw,maxdepth,k,v;
vector <edges> Edge[10001];
vector <edges> edgelist;
//==============function declaration============
void buildtree();
void update(int o,int l,int r);//将编号为k的节点设定为v，当前节点编号为o，范围[l，r] 
void maintain(int o,int l,int r);//更新o节点信息 
void dfs_1(int o);//求出fa dep siz son 
void dfs_2(int o);//求出top w以及各条边在线段树中的编号 
void Set_Negate(int s,int e);//将s->e路径上的所有边变为负值 
void Negate(int o,int l,int r);
int Get_Max_Value(int s,int e);//求出s->e路径上的边的最大值 
void Set_Value(int rank,int value);//将ranklist中第K条边权值设置为value 
int query(int o,int l,int r,bool neg);//
//==============main code=======================
int main()
{  
  string FileName="qtree";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
  clock_t Start_Time=clock();
#endif    
  scanf("%d",&n);
  For(i,1,n)
    Edge[i].clear();
  For(i,1,n*3)
  {
    maxv[i]=-INF;
    minv[i]=INF;
  }
  edgelist.clear();
  int s,e,t;
  For(i,1,n-1)
  {     
    scanf("%d%d%d",&s,&e,&t);
    Edge[s].push_back(edges(s,e,t,i-1));
    Edge[e].push_back(edges(e,s,t,i-1));
    edgelist.push_back(edges(s,e,t,i-1));
    //Edge中的no记录的是该边在edgelist中的位置
    //edgelist中的no记录的是该边在线段树中的位置 
  }
  buildtree();
  char cmd[10];
  while (scanf(" %s",cmd)!=EOF&&cmd[0]!='D')
  {
    if (cmd[0]=='Q')
    {
        scanf("%d%d",&s,&e);
        printf("%d\n",Get_Max_Value(s,e));
    }
    else if (cmd[0]=='C')
    {
      scanf("%d%d",&k,&v);
      Set_Value(k-1,v);
    }
    else 
      pritnf("Init Error!\n");
  }
#ifdef DEBUG  
  clock_t End_Time=clock();
  cout<<endl<<endl<<"Time Used: "<<End_Time-Start_Time<<endl;
#endif    
  return 0;
}
//================fuction code====================
void buildtree()
{
   memset(vis,false,sizeof(vis));
   totw=0; 
   dep[1]=1;
   fa[1]=top[1]=1;
   dfs_1(1);
   memset(vis,false,sizeof(vis));
   dfs_2(1);
   For(i,0,n-2)
   {
     k=edgelist[i].no;
     v=edgelist[i].t;
     update(1,1,n);
   }
}
void dfs_1(int o)//求出fa dep siz son
{
  int m=Edge[o].size()-1;
  int size=1,maxsonsize=0;
  vis[o]=true;
  For(i,0,m)
  {
    edges x=Edge[o][i];
    if (vis[x.e]) 
      continue; 
    dep[x.e]=dep[o]+1;
    fa[x.e]=o;
    dfs_1(x.e);
    if (siz[x.e]>maxsonsize)
    {
      maxsonsize=siz[x.e];                        
      son[o]=x.e;
      
    }
    size+=siz[x.e];
  }
  siz[o]=size;
  return ;
}
void dfs_2(int o)//求出top w以及各条边在线段树中的编号 
{
  vis[o]=true;
  int m=Edge[o].size()-1;
  For(i,0,m)
    if (Edge[o][i].e==son[o])
    {
      edgelist[Edge[o][i].no].no=++totw;
      top[son[o]]=top[o];
      w[son[o]]=totw;
      dfs_2(Edge[o][i].e);
      break;
    }
  For(i,0,m)
  {
    edges x=Edge[o][i];
    if (vis[x.e]||x.e==son[o]) continue;
    edgelist[x.no].no=++totw;
    top[x.e]=x.e;
    w[x.e]=totw;
    dfs_2(x.e);
  }
} 
void update(int o,int l,int r)
{
  int lc=o*2;
  int rc=o*2+1;
  int m=(l+r)/2;
  if (l==r)
  {
    maxv[o]=minv[o]=v;
    return ;
  }
  if (k<=m)
    update(lc,l,m);
  else
    update(rc,m+1,r);
  maintain(o,l,r);
}
void maintain(int o,int l,int r)
{
  int lc=o*2;
  int rc=o*2+1;
  if (l!=r)
  {
    maxv[o]=max(maxv[lc],maxv[rc]);
    minv[o]=min(minv[lc],minv[rc]);
  }
  return ;
}
void Negate(int o,int l,int r)
{
  int lc=o*2;
  int rc=o*2+1;
  int m=(l+r)/2;
  if (y1<=l&&r<=y2)
  {
    negated[o]=!negated[o];
    int temp=maxv[o];
    maxv[o]=-minv[o];
    minv[o]=-temp;
    return ;
  }
  if (negated[o])
  {
    negated[o]=false;
    negated[lc]=!negated[lc];
    negated[rc]=!negated[rc];
    int tmp=minv[lc];
    minv[lc]=-maxv[lc];
    maxv[lc]=-tmp;
    tmp=minv[rc];
    minv[rc]=-maxv[rc];
    maxv[rc]=-tmp;
  }
  if (y1<=m)
    Negate(lc,l,m);
  if (m<y2)
    Negate(rc,m+1,r);
  return ;
  maintain(o,l,r);
}
void Set_Negate(int s,int e)
{
  int u=s,v=e;
  int f1=top[u],f2=top[v];
  while (f1!=f2)
  {
    if (dep[f1]<dep[f2])
      swap(f1,f2),swap(u,v);
    y1=w[f1];y2=w[u];
    Negate(1,1,n) ;
    u=fa[f1];f1=top[u];
  }
  if (u==v)
    return;
  if (dep[u]<dep[v])
    swap(u,v);
  y1=w[son[v]];y2=w[u];
  Negate(1,1,n);
  return ;
}
int Get_Max_Value(int s,int e)
{
  int maxvalue=-INF;
  int u=s,v=e;
  int f1=top[u],f2=top[v];
  while (f1!=f2)
  {
    if (dep[f1]<dep[f2])//f1在上面，将f2向上移动.. 
      swap(f1,f2),swap(u,v);
    y1=w[f1];y2=w[u];
    maxvalue=max(query(1,1,n,false),maxvalue); 
    u=fa[f1];f1=top[u];
  }
  if (u==v) return maxvalue;
  if (dep[u]<dep[v])
    swap(u,v);
  y1=w[son[v]];y2=w[u];
  int temp=query(1,1,n,false);
  if (temp>maxvalue)
    maxvalue=temp;
  return maxvalue;
}
int query(int o,int l,int r,bool neg)
{
  int lc=o*2 ;
  int rc=o*2+1;
  int m=(l+r)/2;
  if (y1<=l&&r<=y2)
  {
    if (neg)
      return -minv[o];
    else
      return maxv[o];
  }
  int maxvalue=-INF;
  if (y1<=m)
    maxvalue=max(query(lc,l,m,neg^negated[o]),maxvalue);
  if (m<y2)
    maxvalue=max(query(rc,m+1,r,neg^negated[o]),maxvalue);
  return maxvalue;
}
void Set_Value(int rank,int value)
{
  k=edgelist[rank].no;
  v=value;
  update(1,1,n);
}