看题目的出门左拐：

　　　　

　　题目大意：给定一棵加权树，实现修改任意节点权值，求两点间路径最大值和权值和的操作。

　　看到题目想都没想就LCT了，敲啊敲、敲啊敲……本来YY着1A的，然后发现WA了……第一个点就WA了……

　　囧……分析了好半天……睡了一觉……猛然想起自己宏定义的INF……

　　原来宏定义INF ~0u>>1然后赋值-INF会出问题的- -

　　我对C++了解不熟……学习了……

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define NIL LCT#define INF 0x7f7f7f7f#define mn 130001#define mm 300000using namespace std;template
          
           inline void gmax(T &a,T b){if(a
           
            
              q;int n,m,a,b,value[mn];char s[10];struct EDGE{ int pnt; EDGE *pre; EDGE (){} EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}}Edge[mm*2],*SP=Edge,*edge[mm];inline void addedge(int a,int b){ edge[a]=new(++SP)EDGE(b,edge[a]); edge[b]=new(++SP)EDGE(a,edge[b]);}struct LinkCutTree{ struct NODE{ int val,maxn,sum; bool root; NODE *left,*right,*father; NODE (){} NODE(int _val,NODE *_left,NODE *_right,NODE *_father): val(_val),left(_left),right(_right),father(_father){root=true;} }LCT[mn],*NP,*node[mn]; void init(){ NP=NIL; NIL->val=NIL->maxn=-INF;NIL->sum=0; NIL->left=NIL->right=NIL->father=NIL; NIL->root=false; } void build(){ q.push(1); node[1]=new(++NP)NODE(value[1],NIL,NIL,NIL); while(!q.empty()){ int i=q.front();q.pop(); for(EDGE *j=edge[i];j;j=j->pre) if(node[j->pnt]!=node[i]->father){ node[j->pnt]=new(++NP)NODE(value[j->pnt],NIL,NIL,node[i]); q.push(j->pnt); } } } void update(NODE *&t){ t->sum=t->left->sum+t->right->sum+t->val; t->maxn=max(t->val,max(t->left->maxn,t->right->maxn)); } void zig(NODE *&t){ NODE *f=t->father,*r=t->right; t->father=f->father; if(f->root){ t->root=true; f->root=false; }else{ if(f->father->left==f) f->father->left=t; else f->father->right=t; } t->right=f,f->father=t,f->left=r,r->father=f; update(f); } void zag(NODE *&t){ NODE *f=t->father,*l=t->left; t->father=f->father; if(f->root){ t->root=true; f->root=false; }else{ if(f->father->left==f) f->father->left=t; else f->father->right=t; } t->left=f;f->father=t,f->right=l,l->father=f; update(f); } void splay(NODE *&t){ while(!t->root){ if(t->father->root){ if(t->father->left==t) zig(t); else zag(t); }else{ if(t->father->father->left==t->father){ if(t->father->left==t) zig(t->father),zig(t); else zag(t),zig(t); }else{ if(t->father->left==t) zig(t),zag(t); else zag(t->father),zag(t); } } } update(t); } void Expose(NODE *&t){ NODE *p=t,*q=NIL; while(p!=NIL){ splay(p); p->right->root=true; p->right=q; p->right->root=false; update(p); q=p,p=p->father; } } void Modify(int t,int key){ node[t]->val=key; update(node[t]); splay(node[t]); } void queryMax(int a,int b){ Expose(node[a]); NODE *p=node[b],*q=NIL; while(p!=NIL){ splay(p); if(p->father==NIL) printf("%d\n",max(p->val,max(p->right->maxn,q->maxn))); p->right->root=true; p->right=q; p->right->root=false; update(p); q=p,p=p->father; } } void querySum(int a,int b){ Expose(node[a]); NODE *p=node[b],*q=NIL; while(p!=NIL){ splay(p); if(p->father==NIL)printf("%d\n",p->right->sum+q->sum+p->val); p->right->root=true; p->right=q; p->right->root=false; update(p); q=p,p=p->father; } }}tree;int main(){ scanf("%d",&n); for(int i=1;i