额，lct一下。。。注意一下细节就可以，，（然并卵，还是搞错）

1 #include
     
        2 #define N 200005  3 #define LL long long  4 #define inf 0x3f3f3f3f  5 #define ls c[x][0]  6 #define rs c[x][1]  7 using namespace std;  8 inline int ra()  9 { 10     int x=0,f=1; char ch=getchar(); 11     while (ch<'0' || ch>'9') {
   if (ch=='-') f=-1; ch=getchar();} 12     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 13     return x*f; 14 } 15 int c[N][2],fa[N],mx[N],mn[N],sum[N],val[N],q[N]; 16 bool tag[N],rev[N]; 17 int n; 18 bool isroot(int x){
   return c[fa[x]][0]!=x && c[fa[x]][1]!=x;} 19 bool which(int x){
   return c[fa[x]][1]==x;} 20 void pushdown(int x) 21 { 22     if (rev[x]) 23     { 24         rev[x]=0; rev[ls]^=1; rev[rs]^=1; swap(ls,rs); 25     } 26     if (tag[x]) 27     { 28         if (ls) sum[ls]=-sum[ls],swap(mx[ls],mn[ls]),mx[ls]=-mx[ls],mn[ls]=-mn[ls],tag[ls]^=1,val[ls]=-val[ls]; 29         if (rs) sum[rs]=-sum[rs],swap(mx[rs],mn[rs]),mx[rs]=-mx[rs],mn[rs]=-mn[rs],tag[rs]^=1,val[rs]=-val[rs]; 30         tag[x]=0; 31     } 32 } 33 void update(int x) 34 { 35     if (x>=n)   //应该把点和边分开判断233，因为点的val会影响答案（应该是这样的）  36     { 37         mx[x]=max(val[x],max(mx[ls],mx[rs])); 38         mn[x]=min(val[x],min(mn[ls],mn[rs])); 39     } 40     else 41     { 42         mx[x]=max(mx[ls],mx[rs]); 43         mn[x]=min(mn[ls],mn[rs]); 44     } 45     sum[x]=sum[ls]+sum[rs]+val[x]; 46 } 47 void rotate(int &x) 48 { 49     int y=fa[x],z=fa[y],nx=which(x),ny=which(y); 50     if (!isroot(y)) c[z][ny]=x; fa[x]=z; 51     c[y][nx]=c[x][!nx]; fa[c[x][!nx]]=y; 52     c[x][!nx]=y; fa[y]=x; update(y); update(x); 53 } 54 void splay(int &x) 55 { 56     int top=0; q[++top]=x; 57     for (int i=x; !isroot(i); i=fa[i]) q[++top]=fa[i]; 58     while (top) pushdown(q[top--]); 59     while (!isroot(x)) 60     { 61         int y=fa[x],z=fa[y]; 62         if (!isroot(y)) 63         { 64             if (which(x)==which(y)) rotate(y); 65             else rotate(x); 66         } 67         rotate(x); 68     } 69 } 70 void access(int x) 71 { 72     for (int t=0; x; t=x,x=fa[x]) 73         splay(x),c[x][1]=t,update(x); 74 } 75 void makeroot(int x) 76 { 77     access(x); splay(x); rev[x]^=1; 78 } 79 void link(int x, int y) 80 { 81     makeroot(x); fa[x]=y; 82 } 83 void change(int x, int w) 84 { 85     makeroot(x); access(x); splay(x);  86     mx[x]=w; mn[x]=w; sum[x]=w; val[x]=w; 87 } 88 void xfs(int x, int y) 89 { 90     makeroot(x); access(y); splay(y); 91     swap(mn[y],mx[y]); mn[y]=-mn[y]; mx[y]=-mx[y]; 92     sum[y]=-sum[y]; val[y]=-val[y]; tag[y]^=1; 93 } 94 int askmax(int x, int y) 95 { 96     makeroot(x); access(y); splay(y); 97     return mx[y]; 98 } 99 int askmin(int x, int y)100 {101     makeroot(x); access(y); splay(y);102     return mn[y];103 }104 int asksum(int x, int y)105 {106     makeroot(x); access(y); splay(y);107     return sum[y];108 }109 int main()110 {111     n=ra();112     mn[0]=inf; mx[0]=-inf;113     for (int i=1; i