JZOJ 6227 Ichi

2 操作显然可以用 Kruskal 重构树的性质转化为重构树上的一棵子树。
又要求属于原树的子树。
那做两个 DFS 序就可以转化为二维的点。

于是就是维护矩阵加，单点查。
直接树状数组套线段树维护。
第一维差分，第二维标记永久化。

代码：

#include <cstdio>
#include <algorithm>
#include <functional>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 1e5;
const int LG = 18;
int n,m,ty,lastans;
struct Edge
{
    int u,v,w;
    inline bool operator>(const Edge &o) const
    {
        return w > o.w;
    }
} e[N + 5];
struct Tree
{
    int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5],edge_tot;
    inline void add(int u,int v,int w)
    {
        to[++edge_tot] = v,val[edge_tot] = w,pre[edge_tot] = first[u],first[u] = edge_tot;
    }
    int fa[N + 5],id[N + 5],sz[N + 5],dfn_tot;
    void dfs(int p)
    {
        sz[p] = 1,id[p] = ++dfn_tot;
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p])
                fa[to[i]] = p,dfs(to[i]),sz[p] += sz[to[i]];
    }
} tree;
struct Kruskal
{
    int tot;
    int a[(N << 1) + 5];
    int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5],edge_tot;
    inline void add(int u,int v)
    {
        to[++edge_tot] = v,pre[edge_tot] = first[u],first[u] = edge_tot;
    }
    int fa[(N << 1) + 5],id[(N << 1) + 5],sz[(N << 1) + 5],f[(N << 1) + 5][LG + 5],dfn_tot;
    void dfs(int p)
    {
        sz[p] = 1,id[p] = ++dfn_tot;
        for(register int i = 1;i <= LG;++i)
            f[p][i] = f[f[p][i - 1]][i - 1];
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ f[p][0])
                f[to[i]][0] = p,dfs(to[i]),sz[p] += sz[to[i]];
    }
    int get(int p)
    {
        return !fa[p] ? p : fa[p] = get(fa[p]);
    }
    int get(int p,int d)
    {
        for(register int i = LG;~i;--i)
            if(f[p][i] && a[f[p][i]] >= d)
                p = f[p][i];
        return p;
    }
} krus;
struct node
{
    long long val;
    int ls,rs;
} seg[(N << 7) + 10];
int rt[N + 5];
inline void update(int l,int r,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    if(l <= tl && tr <= r)
    {
        seg[p].val += k;
        return ;
    }
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
    r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
}
inline long long query(int x,int p,int tl,int tr)
{
    if(!p || tl == tr)
        return seg[p].val;
    int mid = tl + tr >> 1;
    return seg[p].val + (x <= mid ? query(x,seg[p].ls,tl,mid) : query(x,seg[p].rs,mid + 1,tr));
}
inline void update(int x,int l,int r,int k)
{
    for(;x <= n;x += lowbit(x))
        update(l,r,k,rt[x],1,krus.tot);
}
inline long long query(int x,int y)
{
    long long ret = 0;
    for(;x;x -= lowbit(x))
        ret += query(y,rt[x],1,krus.tot);
    return ret;
}
inline void update(int x,int y,int l,int r,int k)
{
    update(x,l,r,k),update(y + 1,l,r,-k);
}
int main()
{
    freopen("ichi.in","r",stdin),freopen("ichi.out","w",stdout);
    scanf("%d%d%d",&n,&m,&ty),krus.tot = n;
    for(register int i = 1;i <= n;++i)
        scanf("%d",krus.a + i);
    for(register int i = 1;i < n;++i)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),tree.add(e[i].u,e[i].v,e[i].w),tree.add(e[i].v,e[i].u,e[i].w);
    sort(e + 1,e + n,greater<Edge>());
    for(register int i = 1;i < n;++i)
    {
        int x = e[i].u,y = e[i].v,w = e[i].w;
        int fx = krus.get(x),fy = krus.get(y);
        if(fx ^ fy)
        {
            krus.fa[fx] = krus.fa[fy] = ++krus.tot;
            krus.add(krus.tot,fx),krus.add(krus.tot,fy);
            krus.a[krus.tot] = w;
        }
    }
    tree.dfs(1);
    for(register int i = krus.tot;i;--i)
        if(!krus.fa[i])
            krus.dfs(i);
    for(register int i = 1;i <= n;++i)
        update(tree.id[i],tree.id[i],krus.id[i],krus.id[i],krus.a[i]);
    int op,v,d,x;
    for(;m;--m)
    {
        scanf("%d",&op);
        if(op == 1)
            scanf("%d",&x),ty && (x = (x + lastans) % n + 1),printf("%lld\n",lastans = query(tree.id[x],krus.id[x]));
        else
        {
            scanf("%d%d%d",&v,&d,&x),ty && (x = (x + lastans) % n + 1);
            int p = krus.get(x,d);
            update(tree.id[x],tree.id[x] + tree.sz[x] - 1,krus.id[p],krus.id[p] + krus.sz[p] - 1,v);
        }
    }
}