---

大家好，我非常喜欢暴力数据结构，于是我用块状树过了这道题目

题目：

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

---

我们可以将树大约划分为\(\sqrt{n}\)块，每个块内维护到块内根节点的路径长度以及点权最大值，而且，显然，我们可以通过寻找它们的\(LCA\)来找到他们路径上的有关信息，而这里我们已经对树进行了分块。

所以在同一个块内的暴跳时间复杂度最坏为\(O(\sqrt{n})\)

在块与块之间的暴跳的时间复杂度最坏为\(O(\sqrt{n})\)

轻松AC本题目

代码中有较详细注释，贴代码

#include
    
     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)//原树边 {    ++cnt1;    e[cnt1].to=v;    e[cnt1].nex=head[u];    head[u]=cnt1;}void add2(int u,int v)//分块后块内树边 {    ++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
    

骗分过样例，暴力出奇迹！！！