题面

---

2

≤

n

≤

2

×

1

0

5

，

1

≤

m

≤

2

×

1

0

5

，

1

≤

l

≤

r

≤

n

，

1

≤

d

≤

1

0

8

2 ≤ n ≤ 2 × 10^5，1 ≤ m ≤ 2 × 10^5，1 ≤ l ≤ r ≤ n，1 ≤ d ≤ 10^8

2≤n≤2×105，1≤m≤2×105，1≤l≤r≤n，1≤d≤108

题解

其实核心思路很简单：我们把原树看成一棵zkw线段树，而不是普通线段树，这样我们修改以及询问的对象就是左哨兵链的右兄弟 以及 右哨兵链的左兄弟，这两条链从叶子一直延申到 lca 的孙子辈。

树链剖分分别维护记录每个点 右兄弟 和 左兄弟 的两棵线段树，时间复杂度

O

(

(

n

+

m

)

log

⁡

2

n

)

O((n+m)\log^2n)

O((n+m)log2n)。

剩下的就是一些细节了。

首先预处理两棵线段树的基本信息，需要让左儿子记录右儿子的区间长度，右儿子记录左儿子的区间长度，然后再根据子树大小（区间长度）重链剖分。剖分后保留原先记录的区间长度不变，也就是说原先的右儿子可能 dfs 序还比左儿子小，但是仍然记录原先左儿子的区间长度、在“左兄弟”线段树上做贡献，并扣牢“右儿子”的帽子。修改以及询问的时候，不因为左右端点实际 dfs 序的颠倒而互换。

针对左右边界，可以加两个哨兵，也可以直接特判。

控制访问到 lca 的孙子辈，比较难且常数较大，我们可以记录儿子辈，然后访问完后把儿子辈的修改 / 贡献撤回。

CODE

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<random>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 400005
#define LL long long
#define ULL unsigned long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
#define FI first
#define SE second
LL read() {
    LL f=1,x=0;int s = getchar();
    while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
    while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}
    return f*x;
}
LL read(int first_c) {
    LL f=1,x=0;int s = first_c;
    while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
    while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}
    return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}
void putnum(LL x) {
    if(!x) {putchar('0');return ;}
    if(x<0) {putchar('-');x = -x;}
    return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
int ls[MAXN],rs[MAXN];
int l[MAXN],r[MAXN];
int fa[MAXN];
int d[MAXN],dfn[MAXN],rr[MAXN],tp[MAXN],tim,id[MAXN];
int lw[MAXN],rw[MAXN];
void dfs0(int x) {
    d[x] = d[fa[x]] + 1;
    tim = 0;
    if(!ls[x]) return ;
    dfs0(ls[x]); dfs0(rs[x]);
    if(l[ls[x]] > l[rs[x]]) swap(ls[x],rs[x]);
    l[x] = l[ls[x]]; r[x] = r[rs[x]];
    int A,B;
    A = lw[rs[x]] = r[ls[x]] - l[ls[x]] + 1;
    B = rw[ls[x]] = r[rs[x]] - l[rs[x]] + 1;
    if(A < B) swap(ls[x],rs[x]);
    return ;
}
void dfs(int x) {
    if(x == ls[fa[x]]) tp[x] = tp[fa[x]];
    else tp[x] = x;
    dfn[x] = ++ tim; id[tim] = x;
    if(ls[x]) dfs(ls[x]);
    if(rs[x]) dfs(rs[x]);
    rr[x] = tim;
    return ;
}
struct it{
    int ls,rs;
    int ct;
    LL sm,lz;
    it(){ls=rs=ct=sm=lz=0;}
}tre[MAXN<<2];
int cnt;
void addd(int a,LL d) {
    tre[a].sm += tre[a].ct *1ll* d;
    tre[a].lz += d; return ;
}
void update(int a) {
    tre[a].sm = tre[tre[a].ls].sm + tre[tre[a].rs].sm;
    tre[a].ct = tre[tre[a].ls].ct + tre[tre[a].rs].ct;
    return ;
}
void pushdown(int a) {
    if(tre[a].lz) {
        addd(tre[a].ls,tre[a].lz);
        addd(tre[a].rs,tre[a].lz);
        tre[a].lz = 0;
    }return ;
}
int maketree(int *p,int l,int r) {
    int a = ++ cnt; tre[a] = it();
    if(l == r) {tre[a].sm = 0; tre[a].ct = p[id[l]];}
    else {
        int md = (l + r) >> 1;
        tre[a].ls = maketree(p,l,md);
        tre[a].rs = maketree(p,md+1,r);
        update(a);
    }
    return a;
}
void addtree(int a,int l,int r,int al,int ar,int d) {
    if(l > r || al > r || ar < l) return ;
    if(al >= l && ar <= r) {
        addd(a,d); return ;
    }
    int md = (al + ar) >> 1; pushdown(a);
    addtree(tre[a].ls,l,r,al,md,d); addtree(tre[a].rs,l,r,md+1,ar,d);
    update(a); return ;
}
LL findtree(int a,int l,int r,int al,int ar) {
    if(l > r || al > r || ar < l) return 0ll;
    if(al >= l && ar <= r) return tre[a].sm;
    int md = (al + ar) >> 1; pushdown(a);
    return findtree(tre[a].ls,l,r,al,md) + findtree(tre[a].rs,l,r,md+1,ar);
}
LL FL = 0;
int RT1,RT2;
void addline(int a,int b,int y) {
    if(a < 1 && b > n) {
        FL += y *1ll* n; return ;
    }
    if(a < 1) {
        while(b) {
            addtree(RT1,dfn[tp[b]],dfn[b],1,tim,y);
            b = fa[tp[b]];
        } return ;
    }
    if(b > n) {
        while(a) {
            addtree(RT2,dfn[tp[a]],dfn[a],1,tim,y);
            a = fa[tp[a]];
        } return ;
    }
    int ld = 0,rd = 0;
    while(tp[a] != tp[b]) {
        if(d[tp[a]] > d[tp[b]]) {
            addtree(RT2,dfn[tp[a]],dfn[a],1,tim,y); ld = tp[a];
            a = fa[tp[a]];
        }
        else {
            addtree(RT1,dfn[tp[b]],dfn[b],1,tim,y); rd = tp[b];
            b = fa[tp[b]];
        }
    }
    if(d[a] <= d[b]) addtree(RT2,dfn[ld],dfn[ld],1,tim,-y);
    if(d[b] <= d[a]) addtree(RT1,dfn[rd],dfn[rd],1,tim,-y);
    if(d[a] < d[b]) addtree(RT1,dfn[a]+2,dfn[b],1,tim,y);
    if(d[b] < d[a]) addtree(RT2,dfn[b]+2,dfn[a],1,tim,y);
    return ;
}
LL findline(int a,int b) {
    if(a < 1 && b > n) {
        return FL;
    }
    LL ans = 0;
    if(a < 1) {
        while(b) {
            ans += findtree(RT1,dfn[tp[b]],dfn[b],1,tim);
            b = fa[tp[b]];
        } return ans;
    }
    if(b > n) {
        while(a) {
            ans += findtree(RT2,dfn[tp[a]],dfn[a],1,tim);
            a = fa[tp[a]];
        } return ans;
    }
    int ld = 0,rd = 0;
    while(tp[a] != tp[b]) {
        if(d[tp[a]] > d[tp[b]]) {
            ans += findtree(RT2,dfn[tp[a]],dfn[a],1,tim); ld = tp[a];
            a = fa[tp[a]];
        }
        else {
            ans += findtree(RT1,dfn[tp[b]],dfn[b],1,tim); rd = tp[b];
            b = fa[tp[b]];
        }
    }
    if(d[a] <= d[b]) ans -= findtree(RT2,dfn[ld],dfn[ld],1,tim);
    if(d[b] <= d[a]) ans -= findtree(RT1,dfn[rd],dfn[rd],1,tim);
    if(d[a] < d[b]) ans += findtree(RT1,dfn[a]+2,dfn[b],1,tim);
    if(d[b] < d[a]) ans += findtree(RT2,dfn[b]+2,dfn[a],1,tim);
    return ans;
}
int main() {
    freopen("pigeons.in","r",stdin);
    freopen("pigeons.out","w",stdout);
    n = read();m = read();
    for(int i = 1;i <= n;i ++) l[i] = r[i] = i;
    for(int i = n+1;i < (n<<1);i ++) {
        s = ls[i] = read();
        o = rs[i] = read();
        fa[s] = fa[o] = i;
    }
    int rt = 0;
    for(int i = n+1;i < (n<<1);i ++) {
        if(!fa[i]) rt = i;
    }
    dfs0(rt);
    dfs(rt);
    RT1 = maketree(lw,1,tim);
    RT2 = maketree(rw,1,tim);
    for(int i = 1;i <= m;i ++) {
        k = read();
        if(k == 1) {
            s = read();o = read();k = read();
            addline(s-1,o+1,k);
        }
        else {
            s = read();o = read();
            AIput(findline(s-1,o+1),'\n');
        }
    }
    return 0;
}