#include <bits/stdc++.h>
// #define int __int128
// #define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 2 * N, mod = 998244353, INF = 0x3f3f3f3f3f3f3f3f, P = 131;
const double eps = 1e-6;
// typedef __int128 LL;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
typedef pair<long long, long long> PLL;
typedef pair<char, int> PCI;
typedef pair<int, char> PIC;
typedef pair<char, char> PCC;
typedef pair<PII, int> PPI;
typedef pair<int, PII> PIP;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;
typedef pair<double, double> PDD;
/*
如果说d = 0的话,那么其实就是普通的树剖+区间修改就可以了
但是现在d可以取到20,那么我们先考虑一下d=1的时候,能否快速解决这个问题?
好像并不是很好做,考虑一下路径长度只有1的情况呢?
举个例子:
图如下:
1 3, 1 8, 3 4, 3 10, 8 2, 4 5, 4 7,10 9, 5 6, 5 11
那么现在我想要修改距离4距离不超过2的所有节点
那么要修改的点有:
6 11, 5 7, 4 10, 3, 1
可以发现这些点可以看成在某棵子树上的同一层,那么我们是不是可以把一层一起修改呢?
又因为这个一层是某棵子树的一层,所以说我们考虑再加一维,就是以某棵子树为根的第几层都被修改了
因为d <= 20,所以说我们后面查询的时候只需要一路往父亲节点走就可以了,然后累加这一层的贡献
比如还是以刚刚那个图为例子,求4的答案,那么就是f[4][0] + f[3][1] + f[1][2]
f[i][j]表示以i为根的子树第j层的贡献是多少,根节点在第0层
那么我们再来看一下具体怎么修改
这里设置多一个变量方便描述,fa[u][i],表示u往上第i父亲节点是谁,同样的fa[u][0]表示自己
那么我们先看一下有哪些是需要修改的:
在fa[u][0]的子树中,d, d - 1, ,,, 0
在fa[u][1]的子树中,d - 1, d - 2, ,,, 0
在fa[u][i]的子树中,d - i, d - i - 1, ,,, 0
在fa[u][d]的子树中,0
但是我们会发现这里面有一些是重复了的,比如说fa[u][0]的d - 2和fa[u][1]的d - 1是重复的
或者说fa[u][1]的d - 1包含了fa[u][0]的d - 2,那么我们是不是就可以把fa[u][0]的d - 2去掉了
那么同理可得,我们可以去删除其他重复,只保留最外围那个,或者说只可能大于等于其他的那个集合
那么最后就变成了:
在fa[u][0]的子树中,d, d - 1
在fa[u][1]的子树中, d - 1, d - 2
在fa[u][i]的子树中, d - i, d - i - 1
那么这里简单来说就是每个节点都是统计两层,然后往上跳一步,边界需要处理一下
那么这个解决完之后,我们再回到一开始的问题,也就是把对点的修改改成了对路径的修改了
现在要修改距离u v路径上距离<=d的所有点,
那么我们使用同样的操作,去掉重复的,保留最外围的,
我们会发现他们的LCA的处理方式就和我们一开始说的那个单点是一样的,然后下面的那些刚好就是每个点对应一层
也就是u的子树中,d,还有fa[u]的子树中, d
那么我们发现除了LCA外,其他路径上的点都是修改d那一层的,那么我们就可以考虑使用树链剖分然后区间修改
对于每个d分别建一颗线段树,那么这里还有一个问题,就是使用树剖求LCA的话只能求出来LCA是谁,但是无法求到LCA的儿子
那么对于这种情况的话,我们可以直接先和下面的一样修改LCA的d,然后在把LCA的d单独减回去就可以了
又因为是区间修改,单点查询,所以使用差分+树状数组也可以,同时常数会小一点,但是使用线段树也能过
官方题解有一种不使用树剖的写法,就是查询是一样的,单点查询,
主要是修改那里,我们要修改的其实就是u -> LCA (不包含LCA)这条路径上的点
以及v -> LCA (不包含LCA)这条路径上的点,那么我们使用树上差分的形式
就是tr[dfn[u]] += d, tr[dfn[LCA]] -= d,这种形式,
使用完差分之后,就是区间查询了,然后那个单点修改的就直接是[dfn[u], INF]这种形式即可
*/
int n, m;
int a[N];
vector<int> g[N];
int sz[N], dep[N], top[N], fa[N], son[N], dfn[N], idx;
struct Node
{
int l, r, w, sum, lazy;
}tr[N * 4][22];
void dfs(int u, int father)
{
sz[u] = 1;
fa[u] = father;
dep[u] = dep[father] + 1;
for (auto v: g[u])
{
if (v == father) continue;
dfs(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
dfn[u] = ++ idx;
if(son[u]) dfs2(son[u], tp);
for (auto v: g[u])
{
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
void build(int u, int l, int r)
{
for (int i = 0; i <= 20; i ++) tr[u][i] = {l, r, 0, 0, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void pushup(int u, int tp)
{
tr[u][tp].sum = tr[u << 1][tp].sum + tr[u << 1 | 1][tp].sum;
}
void pushdown(int u, int tp)
{
if(tr[u][tp].lazy == 0) return ;
tr[u << 1][tp].lazy += tr[u][tp].lazy, tr[u << 1 | 1][tp].lazy += tr[u][tp].lazy;
tr[u << 1][tp].sum += tr[u][tp].lazy * (tr[u << 1][tp].r - tr[u << 1][tp].l + 1),
tr[u << 1 | 1][tp].sum += tr[u][tp].lazy * (tr[u << 1 | 1][tp].r - tr[u << 1 | 1][tp].l + 1);
tr[u][tp].lazy = 0;
}
int query(int u, int l, int r, int tp)
{
if(l <= tr[u][tp].l && tr[u][tp].r <= r) return tr[u][tp].sum;
int mid = tr[u][tp].l + tr[u][tp].r >> 1;
pushdown(u, tp);
int res = 0;
if(l <= mid)res += query(u << 1, l, r, tp);
if(r > mid) res += query(u << 1 | 1, l, r, tp);
pushup(u, tp);
return res;
}
void modify(int u, int l, int r, int x, int tp)
{
if(l <= tr[u][tp].l && tr[u][tp].r <= r)
{
tr[u][tp].lazy += x;
tr[u][tp].sum += x * (tr[u][tp].r - tr[u][tp].l + 1);
return ;
}
int mid = tr[u][tp].l + tr[u][tp].r >> 1;
pushdown(u, tp);
if(l <= mid) modify(u << 1, l, r, x, tp);
if(r > mid) modify(u << 1 | 1, l, r, x, tp);
pushup(u, tp);
}
void solve()
{
cin >> n;
for (int i = 1; i < n; i ++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 1);
build(1, 0, n);
cin >> m;
while (m --)
{
int op, u, v, k, d;
cin >> op >> u;
if(op == 1)
{
int ans = 0;
int t = u;
for (int i = 0; i <= 20; i ++)
{
if(dep[t] - dep[u]== i) ans += query(1, dfn[u], dfn[u], i);
u = fa[u];
}
cout << ans << endl;
}
else
{
cin >> v >> k >> d;
while (top[u] != top[v]) // 说明不在同一条重链上,那么整条重链都要更新
{
if(dep[top[u]] > dep[top[v]]) //u往上跳
{
modify(1, dfn[top[u]], dfn[u], k, d);
u = fa[top[u]];
}
else // v往上跳
{
modify(1, dfn[top[v]], dfn[v], k, d);
v = fa[top[v]];
}
}
//跳出循环,说明两个在同一条重链上
// 要更新到LCA的儿子那里,可以先更新到LCA那里,然后再去掉LCA的贡献
if(dep[u] > dep[v]) swap(u, v);//默认u是LCA
modify(1, dfn[u], dfn[v], k, d);
modify(1, dfn[u], dfn[u], -k, d); //去掉LCA的贡献
//那么下面的就是LCA以及上面的贡献了
for (int i = d; i >= 0; i --)
{
modify(1, dfn[u], dfn[u], k, i);
if(i - 1 >= 0 && u) modify(1, dfn[u], dfn[u], k, i - 1);
u = fa[u];
}
}
}
}
signed main()
{
// freopen("002.in","r",stdin);
// freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
// init(N - 1);
int T = 1;
// scanf("%lld", &T);
// cin >> T;
while (T--) solve();
return 0;
}
/*
*/