当前位置：首页 > news >正文

【BZOJ】【2157】旅游

news 来源：原创 2024/5/16 21:38:31

LCT

　　直到动手写拆边为点的时候才发现根本不会写……去orz了一下Hzwer（话说这题应该也用不着LCT吧……下次再换种姿势写一遍好了）

  1 /**************************************************************
  2     Problem: 2157
  3     User: Tunix
  4     Language: C++
  5     Result: Accepted
  6     Time:668 ms
  7     Memory:2600 kb
  8 ****************************************************************/
  9  
 10 //BZOJ 2157
 11 #include<vector>
 12 #include<cstdio>
 13 #include<cstring>
 14 #include<cstdlib>
 15 #include<iostream>
 16 #include<algorithm>
 17 #define rep(i,n) for(int i=0;i<n;++i)
 18 #define F(i,j,n) for(int i=j;i<=n;++i)
 19 #define D(i,j,n) for(int i=j;i>=n;--i)
 20 using namespace std;
 21 int getint(){
 22     int v=0,sign=1; char ch=getchar();
 23     while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
 24     while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
 25     return v*=sign;
 26 }
 27 /******************tamplate*********************/
 28 const int N=40010,INF=~0u>>2;
 29 int n,m,cnt;
 30 int ed[N];
 31 int c[N][2],fa[N],v[N],sum[N],mn[N],mx[N];
 32 bool rev[N],Not[N];
 33 #define L c[x][0]
 34 #define R c[x][1]
 35 bool not_root(int x){
 36     return c[fa[x]][0]==x || c[fa[x]][1]==x;
 37 }
 38 void rever(int x){
 39     sum[x]=-sum[x]; v[x]=-v[x];
 40     swap(mn[x],mx[x]);
 41     mn[x]=-mn[x];mx[x]=-mx[x];
 42     Not[x]^=1;
 43 }
 44 void Push_up(int x){
 45     mx[x]=max(mx[L],mx[R]);
 46     mn[x]=min(mn[L],mn[R]);
 47     if (x>n){
 48         mx[x]=max(mx[x],v[x]);
 49         mn[x]=min(mn[x],v[x]);
 50     }
 51     sum[x]=sum[L]+sum[R]+v[x];
 52 }
 53 void Push_down(int x){
 54     if (Not[x]){
 55         Not[x]^=1;
 56         if (L) rever(L);
 57         if (R) rever(R);
 58     }
 59     if (rev[x]){
 60         rev[x]^=1; rev[L]^=1; rev[R]^=1;
 61         swap(L,R);
 62     }
 63 }
 64 void rotate(int x){
 65     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
 66     if (not_root(y)) c[z][c[z][1]==y]=x;
 67     fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
 68     c[y][l]=c[x][r]; c[x][r]=y;
 69     Push_up(y);
 70 }
 71 void preview(int x){
 72     if (not_root(x)) preview(fa[x]);
 73     Push_down(x);
 74 }
 75 void splay(int x){
 76     int y;
 77     for(preview(x);not_root(x);rotate(x))
 78         not_root(y=fa[x]) ? rotate(c[y][1]==x^c[fa[y]][1]==y ? x : y),1:1;
 79     Push_up(x);
 80 }
 81 void access(int x,int las=0){
 82     for(;x;splay(x),c[x][1]=las,las=x,x=fa[x]);
 83 }
 84 void makeroot(int x){
 85     access(x),splay(x),rev[x]^=1;
 86 }
 87 void link(int x,int y){
 88     makeroot(x),fa[x]=y;
 89 }
 90 void query(int x,int y){
 91     makeroot(x),access(y),splay(y);
 92 }
 93 int main(){
 94     n=getint();
 95     F(i,0,n) mn[i]=INF,mx[i]=-INF;
 96     int id=n;
 97     F(i,1,n-1){
 98         int x=getint()+1,y=getint()+1,w=getint();
 99         ed[i]=++id;
100         link(x,id); link(y,id);
101         v[id]=sum[id]=mx[id]=mn[id]=w;
102     }
103     m=getint();
104     char cmd[5]; int x,y;
105     F(i,1,m){
106         scanf("%s",cmd);
107         x=getint(); y=getint();
108         if (cmd[0]=='C'){
109             splay(ed[x]),v[ed[x]]=y,Push_up(ed[x]);
110         }
111         else if(cmd[0]=='N')
112             query(x+1,y+1),rever(y+1);
113         else if(cmd[0]=='S')
114             query(x+1,y+1),printf("%d\n",sum[y+1]);
115         else if(cmd[1]=='A')
116             query(x+1,y+1),printf("%d\n",mx[y+1]);
117         else query(x+1,y+1),printf("%d\n",mn[y+1]);
118     }
119     return 0;
120 }