## Praise

## Hello everyone , I really like violent data structures , So I went through the problem with block trees

subject ：

One tree has 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

We can roughly divide the tree into \(\sqrt{n}\) block , The length of the path to the root node in each block and the maximum point weight are maintained , and , obviously , We can do this by looking for their \(LCA\) To find out about their path , And here we've partitioned the trees .

So the worst jump time complexity in the same block is \(O(\sqrt{n})\)

The worst time complexity of jumping between blocks is \(O(\sqrt{n})\)

Relaxed AC This topic

There are more detailed comments in the code , Post code

`#include<bits/stdc++.h>`

using namespace std;

const int maxn=1e5+10;

struct cc{

int to,nex;

}e[maxn],dis[maxn];

int head[maxn],cnt1,h[maxn],cnt2;

void add1(int u,int v)// On the edge of the original tree

{

++cnt1;

e[cnt1].to=v;

e[cnt1].nex=head[u];

head[u]=cnt1;

}

void add2(int u,int v)// After partition, inside the block, beside the tree

{

++cnt2;

dis[cnt2].to=v;

dis[cnt2].nex=h[u];

h[u]=cnt2;

}

int rt[maxn],mx[maxn],sum[maxn],siz[maxn];

int n,m,v[maxn],deep[maxn],len,fa[maxn];

void dfs(int u,int f,int dep)

{

deep[u]=dep;

int tmp=rt[u];

fa[u]=f;

for(int i=head[u];i;i=e[i].nex)

{

int v=e[i].to;

if(v!=f)

{

if(siz[tmp]+1<len)

{

add2(u,v);// The trees in the block are connected to the sides

rt[v]=tmp;

++siz[tmp];

}

dfs(v,u,dep+1);

}

}

}

void build(int u,int num,int vmx)// Maintain the current node , The sum to the root node in the block , Maximum

{

num+=v[u],sum[u]=num;

vmx=max(vmx,v[u]),mx[u]=vmx;

for(int i=h[u];i;i=dis[i].nex)

build(dis[i].to,num,vmx);

}

int query(int a,int b,int tag)

{

int ans1=0;//QSUM

int ans2=-(1<<30);//QMAX

while(a!=b)// It's like doubling , It's just that the distance here is sqrt(n)

{

if(deep[a]<deep[b]) swap(a,b);

if(rt[a]==rt[b])// If they belong to the same block

{

ans1+=v[a];

ans2=max(ans2,v[a]);

a=fa[a];// Because in the same block , The complexity of violent jumping is just O(sqrt(n))

}

else

{

if(deep[rt[a]]<deep[rt[b]]) swap(a,b);// The depth of the block is deeper

ans1+=sum[a];

ans2=max(ans2,mx[a]);

a=fa[rt[a]];// Just jump one block

}

}

ans1+=v[a];

ans2=max(ans2,v[a]);// Update their LCA Value

if(tag==0) return ans2;

else return ans1;

}

void change(int u,int x)

{

v[u]=x;

if(u==rt[u]) build(u,0,-(1<<30));// If it is a root node in a block, the whole block is updated

else build(u,sum[fa[u]],mx[fa[u]]);// If not , It started with his father

}

int main()

{

int x,y;

scanf("%d",&n);

len=sqrt(n);

for(int i=1;i<n;++i)

scanf("%d%d",&x,&y),add1(x,y),add1(y,x);// On the edge of the original tree

for(int i=1;i<=n;++i)

scanf("%d",&v[i]),rt[i]=i;

dfs(1,0,0);

for(int i=1;i<=n;++i)

if(rt[i]==i)

build(i,0,-(1<<30));

scanf("%d",&m);

char opt[30];

for(int i=1;i<=m;++i)

{

scanf("%s%d%d",opt,&x,&y);

if(opt[1]=='M')//QMAX

printf("%d\n",query(x,y,0));//01 Maintenance questions

else if(opt[1]=='S')//QSUM

printf("%d\n",query(x,y,1));//01 Maintenance questions

else //CHANGE

change(x,y);

}

return 0;

}

### I've cheated the samples , Violence works wonders ！！！

## Luogu P2590 [ZJOI2008] More related articles on tree statistics

- Luogu ——P2590 [ZJOI2008] Statistics of trees （ Tree chain dissection template practice ）
P2590 [ZJOI2008] Statistics of trees 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: inquiry ...

- Luogu P2590 [ZJOI2008] Statistics of trees [ The tree chain splits ]
Subject portal Statistics of trees Title Description One tree has 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 ...

- Luogu P2590 [ZJOI2008] Statistics of trees Answer key The tree chain splits + Line segment tree
Topic link :https://www.luogu.org/problem/P2590 Tree chain partition template problem . The dissection process uses the following 7 It's worth : fa[u]:u The parent node number of : dep[u]:u The depth of the : size[u]: ...

- Luogu P2590 [ZJOI2008] Statistics of trees （ The tree chain splits ）
There is... 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 ...

- [ Luogu P2590][ZJOI2008] Statistics of trees
The main idea of the topic : A tree , Three operations are supported , $CHANGE\;u\;t:$ Put the node $u$ The weight of is changed to $t$ $QMAX\;u\;v:$ Ask from point $u$ point-to-point $v$ The maximum weight of the node on the path of $QSUM\;u\;v:$ ...

- Luogu ——P2590 [ZJOI2008] Statistics of trees
https://www.luogu.org/problem/show?pid=2590#sub Title Description One tree has n Nodes , The numbers are 1 To n, Each node has a weight w. We're going to ask you in the form of ...

- Luogu .2590.[ZJOI2008] Statistics of trees ( The trees are divided into blocks )
Topic link Update: This kind of block writing ... It can get stuck ... It seems that there is no reliable tree block writing method ... /* Block the nodes on the tree , Each point records dep,fa,val,Max,Sum,Max,Sum Indicates that the current point is within the block ...

- P2590 [ZJOI2008] Statistics of trees （ The tree chain splits ）
P2590 [ZJOI2008] Statistics of trees Although it's an entry tree profile template But I finally 1A 了 ( Cry ) Too lazy to write ( flee #include<iostream> #include<cstdio> ...

- P2590 [ZJOI2008] Statistics of trees （LCT）
P2590 [ZJOI2008] Statistics of trees Title Description One tree has 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 : hold ...

## Random recommendation

- A deserted Saturday -PHP Object oriented （ 3、 ... and ）
hi It's Kaisen's Saturday again . Two weeks of accumulated clothing , Finally, it's almost finished . I came to learn something in the afternoon ~~ 1.PHP object-oriented ( 3、 ... and ) Four .OOP Advanced practice of 4.3 Static- Static members <?phpdate_def ...

- ubuntu Common command recordsets
1. Find the file containing a string in the current directory #find ./ -type f |xargs grep "string" 2. Find files #find ./ -name filename 3. ...

- TaskTracker Memory manager on node
Hadoop The biggest advantage of the platform is to make full use of the cheap PC machine , This makes the working nodes in the cluster have an important problem —— Where the node is located PC Memory resources are limited ( The work node here refers to TaskTracker node ), When you're on a mission ...

- Data Base sqlServer DataReader And DataSet The difference between
sqlServer DataReader And DataSet The difference between Compare from the following aspects : 1. Connect to database : DataReader: Connection oriented , read-only , Only in the , You can only read forward , Disconnect after reading the data : DataS ...

- The browser appears Cannot set property 'onclick' of null The problem of
Part1: When js Files in head Inside , If it's bound onclick event , There will be such a mistake , Because W3School The way to write is that the browser loads the button node first js, So when the browser parses from the top down , Can't find on ...

- Overload&Override
Overload&Override overload-– heavy load Method overloading is in a class , You can define more than one with the same name , But the parameters are different . Invocation time , The corresponding method will be selected according to different parameter tables . gauge be : With two ...

- C# Serial port communication ：2 Auto connect
Last time I talked about the general structure of the agreement , This time, let's talk about how to realize the brake connection serial port ( When you connect the device , How to make the software automatically identify whether it is the target device , Of course, this needs the upper computer and the lower computer to complete together , Here we only discuss the upper computer part ) Let's make a deal first : Frame head ...

- Python The foundation re modular （ Regular expressions ）
By its very nature , Regular expressions ( or RE) It's a small . Highly specialized programming language ,( stay Python in ) It's embedded in Python in , And pass re Module implementation . The regular expression pattern is compiled into a series of bytecodes , And then by C Compiling ...

- Linux Text processing tools grep,sed,awk
grep.sed and awk It's all text processing tools , Although they are all text processing tool lists, they all have their own advantages and disadvantages , One text processing command cannot be completely replaced by another , Otherwise, there won't be three text processing commands . It's just , By comparison ,sed and awk More functional ...

- New Concept English Two 18 46
$ text 44 Through the forest 451. Mrs. Anne Sterling did not think of the risk she was taking when she ran through a ...