← Home
#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;
}
/*
 
*/