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

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

  6. Overload&amp;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 ...

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