\(2\) 操作显然可以用 Kruskal 重构树的性质转化为重构树上的一棵子树。
又要求属于原树的子树。
那做两个 DFS 序就可以转化为二维的点。
于是就是维护矩阵加，单点查。
直接树状数组套线段树维护。
第一维差分，第二维标记永久化。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
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);
}
}
}