1036: [ZJOI2008] Statistics of trees Count

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 10677  Solved: 4313
[Submit][Status][Discuss]

Description

One
It's on a tree n Nodes , The numbers are 1 To n, Each node has a weight w. We're going to ask you to do something about this tree in the following form : I. CHANGE u t :
Put the node u The weight of is changed to t II. QMAX u v: Ask from point u point-to-point v The maximum weight of the node on the path of III. QSUM u v:
Ask from point u point-to-point v The weight sum of nodes on the path of Be careful : From the point of u point-to-point v The nodes on the path of include u and v In itself

Input

transport
The first line in is an integer n, Represents the number of nodes . Next n –
1 That's ok , Each row 2 It's an integer a and b, Representation node a And nodes b There's an edge between them . Next n That's ok , One integer per row , The first i The whole number of lines wi Representation node i A weight . Next 1 That's ok , It's an integer
q, Represents the total number of operations . Next q That's ok , One operation per line , With “CHANGE u t” perhaps “QMAX u v” perhaps “QSUM u v” Given in the form of .
about 100% The data of , Guarantee 1<=n<=30000,0<=q<=200000; The weight of each node is guaranteed in the midway operation w stay -30000 To
30000 Between .

Output

For each “QMAX” perhaps “QSUM” The operation of , Each line outputs an integer to represent the result to be output .

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

【 Ideas 】

The tree chain splits , Line segment tree

Line segment tree : Interval query max sum , Single point operation set.

Just pay attention to negative numbers =-=.

【 Code 】

 #include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int N = +;
const int INF = 1e9; struct Node {
int mx,sum;
Node() {mx=-INF,sum=;}
}T[N<<]; int n,q,z;
char s[];
vector<int> g[N];
//INIT
int top[N],son[N],dep[N],fa[N],siz[N],w[N];
void dfs1(int u) {
son[u]=; siz[u]=;
for(int i=;i<g[u].size();i++) {
int v=g[u][i];
if(v!=fa[u]) {
fa[v]=u , dep[v]=dep[u]+;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int tp) {
top[u]=tp; w[u]=++z;
if(son[u]) dfs2(son[u],tp);
for(int i=;i<g[u].size();i++) {
int v=g[u][i];
if(v!=fa[u] && v!=son[u]) dfs2(v,v);
}
}
//SEGMENT TREE
void update(int u,int L,int R,int r,int x) {
if(L==R) T[u].mx=T[u].sum=x;
else {
int M=(L+R)>>,lc=u<<,rc=lc|;
if(r<=M) update(lc,L,M,r,x);
else update(rc,M+,R,r,x);
T[u].mx=max(T[lc].mx,T[rc].mx);
T[u].sum=T[lc].sum+T[rc].sum;
}
}
int qsum,qmx;
void query(int u,int L,int R,int l,int r) {
if(l<=L && R<=r)
qsum+=T[u].sum , qmx=max(qmx,T[u].mx);
else {
int M=(L+R)>>;
if(l<=M) query(u<<,L,M,l,r);
if(M<r) query(u<<|,M+,R,l,r);
}
}
// The tree chain splits
int query(int u,int v,int flag) {
int sum=,mx=-INF;
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
qsum= , qmx=-INF;
query(,,z,w[top[u]],w[u]);
sum+=qsum , mx=max(mx,qmx);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
qsum= , qmx=-INF;
query(,,z,w[u],w[v]);
sum+=qsum , mx=max(mx,qmx);
return flag? sum:mx;
} void read(int& x) {
char c=getchar(); int f=; x=;
while(!isdigit(c)) {if(c=='-')f=-;c=getchar();}
while(isdigit(c)) x=x*+c-'',c=getchar();
x*=f;
}
int main() {
read(n);
int u,v,x;
FOR(i,,n-) {
read(u),read(v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(),dfs2(,);
FOR(i,,n)
read(x) , update(,,z,w[i],x);
read(q);
while(q--) {
scanf("%s",s);
read(u),read(v);
if(s[]=='C') update(,,z,w[u],v);
else
if(s[]=='M') printf("%d\n",query(u,v,));
else printf("%d\n",query(u,v,));
}
return ;
}

bzoj 1036 [ZJOI2008] Statistics of trees Count( The tree chain splits , Line segment tree ) More articles about

  1. BZOJ.1036 [ZJOI2008] Statistics of trees Count ( Point weight tree chain dissection The line segment tree maintains and matches the maximum value )

    BZOJ.1036 [ZJOI2008] Statistics of trees Count ( The tree chain splits The line segment tree maintains and matches the maximum value ) Problem analysis ( The title picture comes from here ) The problem of the first tree chain partition , Talk about your understanding . The problem that tree chain partition can solve is , subject ...

  2. 【bzoj1036】 Statistics of trees [ZJOI2008] The tree chain splits + Line segment tree

    Subject portal :1036: [ZJOI2008] Statistics of trees Count This is my first time to make a tree section , Although the code is a little long , however “ It's a good fight ”, And it took less than 1.5h+, Again and again ! One submission AC!( Before ...

  3. BZOJ.1758.[WC2010] Reconstruction plan ( Fractional programming Point divide and conquer A monotonous queue / A long chain splits Line segment tree )

    Topic link BZOJ Luogu Point divide and conquer A monotonous queue : Two points answer , And then judge whether there is a length in \([L,R]\) The path satisfies the weight and nonnegative . It can be divided . about ( From the current root node ) Depth is \(d\) A path for , You can use other subtrees ...

  4. BZOJ.4034 [HAOI2015] Tree operation ( Point weight tree chain dissection Line segment tree )

    BZOJ.4034 [HAOI2015] Tree operation ( Point weight tree chain dissection Line segment tree ) Problem analysis There's a tree that counts N The tree of , With a little 1 Root , And the tree point has edge weight . Then there is M individual operation , Divided into three : operation 1 : Take a node ...

  5. BZOJ 3672[NOI2014] Ticket purchase ( The tree chain splits + The line tree maintains the convex hull + Slope optimization ) + BZOJ 2402 Tao Tao's problem II ( The tree chain splits + The line tree maintains the convex hull + Fractional programming + Slope optimization )

    Preface At the beginning, I felt numb when I looked at the two questions , Later, let's look at the solution , I found it very understandable , It's just that the code is a little long . BZOJ 3672[NOI2014] Ticket purchase Chinese questions , On the meaning of the title : BZOJ 3672[NOI2014] Ticket purchase set up f(i)f( ...

  6. bzoj 4196 [Noi2015] Package manager ( The tree chain splits + Line segment tree )

    4196: [Noi2015] Package manager Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 2852  Solved: 1668[Submit][Sta ...

  7. bzoj 2157: tourism 【 The tree chain splits + Line segment tree 】

    Naked tree chain dissection + Line segment tree But pay attention to one thing -- I WA It took several times to find that after taking the opposite number max Values and min Values are to be exchanged -- #include<iostream> #include<cstdio& ...

  8. BZOJ 3589 Dynamic trees ( The tree chain splits + Line segment tree )

    Preface as everyone knows ,90%90\%90% It has nothing to do with the solution . The question There is a tree with roots , Two kinds of operations . One is to add a same number to the weight of each point in the subtree , The other is to query the sum of the weights of the union of multiple paths . analysis It's easy to see that it's tree chaining + ...

  9. 【BZOJ-2325】 The battle of Daoguan The tree chain splits + Line segment tree

    2325: [ZJOI2011] The battle of Daoguan Time Limit: 40 Sec  Memory Limit: 256 MBSubmit: 1153  Solved: 421[Submit][Statu ...

  10. 【BZOJ2243】[SDOI2011] dyeing The tree chain splits + Line segment tree

    [BZOJ2243][SDOI2011] dyeing Description Given a tree with n Rootless trees with nodes and m Operations , Operation has 2 class : 1. The nodes a To the node b All the points on the path are colored c: 2. Ask nodes a To the node b On the way ...

Random recommendation

  1. could not build module &#39;XXXXXXXX&#39; perhaps error: expected identifier or &#39;(&#39; . A bunch of strange mistakes ———— Root cause of error

    A bunch of strange mistakes :️could not build module 'XXXXXXXX' ️error: expected identifier or '(' ️EDIT Setting Pr ...

  2. solve ssh Disconnect due to too long idle time after login

     ++++++++++++++++++++++++++++ #!/usr/bin/env bash password_5="Uxxx7"host_5="129.x.x.1 ...

  3. Web Services and C# Enums - From the Internet

    Web Service Transparency .NET support for web services is excellent in creating illusion of transpar ...

  4. ( turn ) Java What programmers should know 10 A debugging technique

    The original address :http://www.csdn.net/article/2012-09-03/2809495-java-debugging-tips-with-eclipse Debugging can help identify and solve the problems of the application ...

  5. Python Dictionaries (Dictionary) has_key() Method

    describe Python Dictionaries (Dictionary) has_key() Function is used to determine whether the key exists in the dictionary , If the key is in the dictionary dict Back in true, Otherwise return to false. grammar has_key() Method syntax :dic ...

  6. css Locate the mask below the image

    The effect needed is shown in the picture , Put a mask on the bottom of the picture : html: <div class="listContent"> <div><img src="imag ...

  7. Java Design patterns - Detailed explanation of single mode ( Expand )

    Singleton pattern triggers related collation How to break the singleton mode Example : /** * If you break singleton mode * * @author sunyang * @date 2018/11/13 20:14 */ public class ...

  8. Oracle no TOP, how to get top from order

    On ROWNUM and Limiting Results Our technologist explains how ROWNUM works and how to make it work fo ...

  9. hadoop mapreduce A simple example

    This example counts The number of words separated by spaces (  This Main.mian The way to start is hadoop 2.0 Writing .1.0 Dissimilarity ) Directory structure : The use of maven : Here is maven rely on . <de ...

  10. We suggest you use Java 8 Date 、 Time , Instead of java.util.Date

    We suggest you use Java 8 Date . Time , Instead of java.util.Date. See... For detailed reasons : How to be in Java 8 Happily deal with dates and times in So in summary , java.util.Date Too messy , Such as Month from 0 Start . ...