树链剖分

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))

//k<<1（节点k的左子树下标）
#define lson l,mid,rt<<1
//k<<1|1（节点k的右子树下标）
#define rson mid+1,r,rt<<1|1

#define ll long long
const int N=100005;
int n,m,tot,cnt;
int first[N];
ll sum[N<<2],w[N],wt[N];
int d[N],fa[N],siz[N],son[N],top[N],id[N],rk[N];
struct node //节点：这道题没有边权值，所以没有w（价值）
{
    int v; //终点
    int nex;
}e[N<<1];

void adde(int u,int v)    //链式向前星，tot从0开始存，没有边权值，所以不用存
{
    e[tot].v=v;          //记录u节点的终点
    e[tot].nex=first[u]; //表示与第i条边同起点的下一条边存储的位置
    first[u]=tot++;
}
void init()
{
    tot = 0; //tot记录链式向前星
    cnt=0;
    memset(first,-1,sizeof(first)); //链式向前星的head数组，一般初始化为-1
    memset(son,0,sizeof(son));
}

void dfs1(int u,int pre,int depth) //处理 d,fa,siz,son 数组 -> 分别是深度、父亲、大小（包含自己本身）、重儿子节点
{
    d[u]=depth; //记录u节点的深度            -》深度
    fa[u]=pre;  //记录u的父亲节点            -〉父亲
    siz[u]=1;   //记录u的大小（这个点本身size=1） -》大小

    for(int i=first[u] ; i!=-1 ; i=e[i].nex) //遍历i节点
    {
        int v=e[i].v;          //v是是与i节点连接的点
        if(v==pre) continue;   //如果v是i的父亲节点，直接continue
        dfs1(v,u,depth+1);     //层次深度+1，以v为当前节点，u为父亲节点，深度+1
        siz[u]+=siz[v];        //父亲节点的大小=本身的大小+子节点的大小
        if(siz[v]>siz[son[u]]) //如果 子节点v的大小 比 父亲节点的重儿子节点的大小 大，那么更新重儿子节点
        {
            son[u]=v;
        }
    }
}

void dfs2(int u,int t) //当前节点，重链顶端 ——》处理 top（当前节点链的顶端） id（保存树中每个节点剖分呢以后的新编号） rk（对应节点） wt 数组
{
    top[u]=t;     //u节点的顶端是t

    /*id和rk正好相互对应*/
    id[u]=++cnt;  //保存树中每个节点剖分后的新编号
    rk[cnt]=u;    //保存当前dfs标号在树中所对应的节点

    wt[cnt]=w[u]; //储存当前的价值

    if(!son[u]) return; //如果是叶子节点（没有重儿子），直接返回

    /*如果不是叶子节点，一定是有重儿子的。
     我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/

    dfs2(son[u],t);

    for(int i=first[u];i!=-1;i=e[i].nex) //对重儿子进行遍历过后，再对当前节点的其余儿子进行遍历
    {
        int v=e[i].v;  //v是与i节点相连的节点
        if(v!=son[u] && v!=fa[u]) //如果v不是重儿子，且v不是u的父亲节点
        {
            dfs2(v,v); //一个点位于轻链底端，那么他的top必然是自己本身
        }
    }
}

//更新函数，这里是实现最大值，同理可以变成最小值，区间和等
void pushup(int rt)
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1]; //当前节点的sum=两个儿子节点的sum之和
}

/*每个叶子节点的值就是数组的值，每个非叶子节点的度都为2，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值*/

//递归方式建树
void build(int l,int r,int rt) //建线段树，一开始l=1,r=n,rt=1,rt表示当前需要建立的节点
{
    if(l==r) //如果左端点==右端点，即为叶子节点，直接赋值即可
    {
        sum[rt]=wt[l];
    }
    else
    {
        int mid=(l+r)>>1; //m为中间点，左儿子的节点区间为[l,m]，右儿子的节点区间为[m+1,r]
        build(lson); //递归构造左儿子节点
        build(rson); //递归构造右儿子节点
        pushup(rt);  //更新父节点
    }
}



ll query(int L,int R,int l,int r,int rt) // 查询[L,R]区间的和 ,l=1,r=n,rt=1
{
    if(l>=L && r<=R) return sum[rt]; //如果需要查询的区间在l和r之间，直接返回当前节点的sum值就可以了
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=query(L,R,lson);
    if(mid<R) ans+=query(L,R,rson);
    return ans;
}

void update(int L,int R,int l,int r,int rt) //[L,R]区间开根号 ，rt为节点下标
{
    if(sum[rt]==r-l+1) return; //区间内所有点都为1，就不用再往下更新了
    if(l==r) //如果左端点==右端点，为叶子节点，直接更新它的值就可以了
    {
        sum[rt]=(ll)sqrt(sum[rt]); //
    }
    else
    {
        int mid=(l+r)>>1;
        if(L<=mid) update(L,R,lson); //如果需要更新的节点在左子树区间
        if(mid<R) update(L,R,rson);  //如果需要更新的节点在右子树区间
        pushup(rt);                  //更新父节点的值
    }
}

void uprange(int x,int y) //操作1 : x到y的最短路径开根
{
    while(top[x]!=top[y]) //如果x和y的顶端不相等，那么进行更新
    {
        if(d[top[x]]<d[top[y]]) swap(x,y); // 如果x顶端比y顶端深度要小（就是x在上面），交换x和y，就是保证x在下面
        update(id[top[x]],id[x],1,n,1);    // x顶端到x之间开根号
        x=fa[top[x]];                      // x=x顶端的父亲节点，x的值不断向上找，直到x和y拥有一样的顶端
    }

    //最后x顶端和y顶端相等
    if(d[x]>d[y]) swap(x,y);     //如果x的深度大于y的深度，那么交换x和y的值，保证x在下面
    update(id[x],id[y],1,n,1);   //x和y之间开根号
}

//查询操作，其实是个LCA，不过这里是用了top来进行加速，因为top可以直接跳转到该重链的起始节点，轻链没有起始节点之说，他的top就是它自己。
//需要注意的是，每次循环只能跳一次并且让节点深的那个来跳到top父亲节点的位置，避免两个一起跳从而擦肩而过
ll querange(int x,int y) //操作2 : 求x到y的最短路径的和
{
    ll ans=0;
    while(top[x]!=top[y]) //如果x和y的链顶端节点不相等，那么进行更新
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);  //如果x顶端比y顶端深度要小（就是x在上面），交换x和y，就是保证x在下面（保证x的节点深）
        ans+=query(id[top[x]],id[x],1,n,1); //求 x的顶端 到 x 之间的和（因为x顶端的id一定比x的id小）
        x=fa[top[x]];                       //x=x顶端的父亲节点
    }
    //直到x和y拥有一样的顶端为止
    if(d[x]>d[y]) swap(x,y);
    ans+=query(id[x],id[y],1,n,1);         //ans += x到y区间和
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m); //树上的节点 + 操作数量
    init();               //初始化
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]); //将第i个节点的值输入
    }
    int u,v;
    for(int i=1;i<n;i++) //原来的树
    {
        scanf("%d%d",&u,&v); //输入两个节点，将两个节点连接起来（双向边）
        adde(u,v);
        adde(v,u);
    }

    dfs1(1,0,1); //第一遍dfs ，从根节点1开始，父亲是0，深度是1
    dfs2(1,1);   //第二遍dfs ，从根节点1开始，重链顶端也是1

    /*两遍dfs就是树链剖分的主要处理，通过dfs我们已经保证重链上各个节点dfs序连续。
     那么可以想到，我们可以通过数据结构，以线段树为例，来维护一条重链的信息。*/

    build(1,n,1); //建立线段树

    int op,x,y; //op是哪个操作，x，y分别是操作的两个点
    while(m--)
    {
        scanf("%d %d %d",&op,&x,&y);
        if(op==0) uprange(x,y); //开根号向下取整
        else if(op==1) printf("%lld\n",querange(x,y)); //计算x到y之间的和
    }
    return 0;
}