D

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6547

题意：给定一棵树，有两种操作，路径点权和查询，路径上每个点开根号向下取整。

思路：树链操作，1e9最多开10次根号就是1了，我们只需要开一个变量维护一段区间是不是全都是1就可以了。

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"algorithm"
using namespace std;
typedef long long ll;
const int N = 200010;

int n,q,root,mod;
int head[N],ver[N],Next[N],tot;///树的结构存储
ll val[N];///存储每个结点的信息
int d[N],son[N],far[N],Size[N];///结点的深度，重儿子，祖先
ll sum[N * 4];///线段树上的结点值，maxx,sum值
int dfn[N],top[N],id[N];///存储dfs序，top是条链的祖先，id是每个结点在dfn中序列的下标位置
int cnt;///表示的是dfs序列的最后一个位置
int laze[N * 4],now[N * 4];
int num[N * 4];

void add(int x,int y){ ///添加树边
    ver[++ tot] = y;  Next[tot] = head[x]; head[x] = tot;
}

void Build_Tree(int id,int l,int r)
{
    laze[id] = now[id] = 0; num[id] = 0;
    if(l == r)
    {
        laze[id] = 0; now[id] = 0;
        sum[id] = val[dfn[l]]; return ;
    }
    int mid = (l + r) >> 1;
    Build_Tree(id * 2,l,mid);
    Build_Tree(id * 2 + 1,mid + 1,r);
    sum[id] = sum[id * 2] + sum[id * 2 + 1];
    return ;
}


void Update(int id,int L,int R,int l,int r)///将loc上的值进行更新
{
    if(l <= L && r >= R && num[id] >= 6)
    {
        return ;
    }
    if(L == R)
    {
        sum[id] = (ll)sqrt(sum[id]);
        num[id] ++;
        return ;
    }
    int mid = (L + R) >> 1;
    if(l <= mid) Update(id * 2,L,mid,l,r);
    if(r > mid) Update(id * 2 + 1,mid + 1,R,l,r);
    sum[id] = sum[id * 2] + sum[id * 2 + 1];
    now[id] = min(now[id * 2],now[id * 2 + 1]);
    return ;
}

ll Query_sum(int id,int L,int R,int l,int r)///查询[l,r]区间和
{
    if(L > r || R < l) return 0;
    if(l <= L && r >= R)
        {
            return sum[id];
        }
    int mid = (L + R) >> 1;
    ll ans = Query_sum(id * 2,L,mid,l,r) + Query_sum(id * 2 + 1,mid + 1,R,l,r);
    return ans;
}

void dfs1(int u,int f,int dep)///dfs1指在处理d数组，son数组，far数组,Size数组
{
    d[u] = dep; far[u] = f;
    Size[u] = 1; son[u] = -1;
    for(int i = head[u]; i; i = Next[i]){
        int v = ver[i];
        if(v == f) continue;
        dfs1(v,u,dep+1);
        Size[u] += Size[v];
        if(son[u] == -1 || Size[son[u]] < Size[v])
           son[u] = v;
    }
}

void dfs2(int u,int T)///旨在处理重链，和dfs序列
{
    dfn[++ cnt] = u;id[u] = cnt;
    top[u] = T;
    if(son[u] == -1) return ;
    dfs2(son[u],T);
    for(int i = head[u]; i; i = Next[i]){
        int v = ver[i];
        if(v != son[u] && v != far[u]){
            dfs2(v,v);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld",&val[i]);
    }
    for(int i = 1; i < n; i ++)
    {
        int x,y; scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    cnt = 0;root = 1;
    dfs1(root,root,1);
    dfs2(root,root);
    Build_Tree(1,1,n);

    while(q --)
    {
       int op; scanf("%d",&op); op ++;
       if(op == 1)
       {
           int u,v; scanf("%d%d",&u,&v);
           int fu = top[u],fv = top[v];
           int ans = 0;
            while(fu != fv)
            {
                if(d[fu] >= d[fv])
                {
                    Update(1,1,n,id[fu],id[u]);
                    u = far[fu]; fu = top[u];
                } else {
                    Update(1,1,n,id[fv],id[v]);
                    v = far[fv]; fv = top[v];
                }
            }
            if(id[u] < id[v]) Update(1,1,cnt,id[u],id[v]);
            else Update(1,1,cnt,id[v],id[u]);
       }
       if(op == 2)
       {
           int u,v; scanf("%d%d",&u,&v);
           int fu = top[u],fv = top[v];
            ll ans = 0;
            while(fu != fv)
            {
                if(d[fu] >= d[fv])
                {
                    ans += Query_sum(1,1,n,id[fu],id[u]);
                    u = far[fu]; fu = top[u];
                } else {
                    ans += Query_sum(1,1,n,id[fv],id[v]);
                    v = far[fv]; fv = top[v];
                }
            }
            if(id[u] < id[v]) ans += Query_sum(1,1,cnt,id[u],id[v]);
            else ans += Query_sum(1,1,cnt,id[v],id[u]);
            printf("%lld
",ans);
       }
    }
}