## 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.

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];
void add1(int u,int v)// On the edge of the original tree
{
++cnt1;
e[cnt1].to=v;
}
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;
{
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)
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;
for(int i=1;i<=m;++i)
{
scanf("%s%d%d",opt,&x,&y);
if(opt=='M')//QMAX
printf("%d\n",query(x,y,0));//01 Maintenance questions
else if(opt=='S')//QSUM
printf("%d\n",query(x,y,1));//01 Maintenance questions
else //CHANGE
change(x,y);
}
return 0;
}


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

1. 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 ...

2. 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 ...

3. 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]: ...

4. 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 ...

5. [ 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:$ ...

6. 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 ...

7. 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 ...

8. 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> ...

9. 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

1. 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 ...

2. 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. ...

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 ...

4. 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 ...

5. The browser appears Cannot set property &#39;onclick&#39; 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-– 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 ...

7. 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 ...

8. 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 ...

9. 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 ...

10. 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 ...