题目地址：BZOJ：Problem 3589. — 动态树

题目描述

小明在楼下种了一棵动态树, 该树每天会在某些节点上长出一些果子. 这棵树的根节点为1, 它有n个节点, n-1条边.
别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件
事件0:
这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子.
事件1:
小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和. 注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次.
初始时, 每个节点上都没有果子.

输入输出格式

输入格式：
第一行一个整数n(1<=n<=200,000), 即节点数.
接下来n-1行, 每行两个数字u, v. 表示果子u和果子v之间有一条直接的边. 节点从1开始编号.
在接下来一个整数nQ(1<=nQ<=200,000), 表示事件.
最后nQ行, 每行开头要么是0, 要么是1.
如果是0, 表示这个事件是事件0. 这行接下来的2个整数u, delta表示以u为根的子树中的每个节点长出了delta个果子.
如果是1, 表示这个事件是事件1. 这行接下来一个整数K(1<=K<=5), 表示这次询问涉及K个树枝. 接下来K对整数u_k, v_k, 每个树枝从节点u_k到节点v_k. 由于果子数可能非常多, 请输出这个数模2^31的结果.

输出格式：
对于每个事件1, 输出询问的果子数.

输入输出样例

输入样例#1：

5
1 2
2 3
2 4
1 5
3
0 1 1
0 2 3
1 2 3 1 1 4

输出样例#1：

13

说明

1 <= n <= 200,000, 1 <= nQ <= 200,000, K = 5.
生成每个树枝的过程是这样的:先在树中随机找一个节点, 然后在这个节点到根的路径上随机选一个节点, 这两个节点就作为树枝的两端.

题解

又是树链信息，套树剖。考虑线段树维护区间和，然后使用打标记的形式来处理链并的问题。链上的点都打上标记，只有打标记的点的权值才会计入答案，这个线段树写是容易的。记得每次清空这次打过的标记。
至于那个取模，模数是2147483648，我们可以用int自然溢出以后对2147483647取与，这样就能把符号位搞掉，得到取模后的答案，减小常数。
吐槽：不要用memset处理很大的数组，会TLE。线段树做是O(\log n)比memsetO(n)优。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 200005;

int n, q, ut, vt, op, xt, kt;
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
std::vector<int> gra[MAXN];

inline void addedge(int u, int v) {
    gra[u].push_back(v);
    gra[v].push_back(u);
}

inline void dfs1(int u) {
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa[u]) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v] + 1;
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

inline void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    ptn[dfn[u]] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int val[MAXN << 2], sum[MAXN << 2], add[MAXN << 2], tag[MAXN << 2];

inline void pushdown(int o, int l, int r) {
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(add[o]) {
        add[lch] += add[o];
        add[rch] += add[o];
        val[lch] += add[o] * (mid - l + 1);
        val[rch] += add[o] * (r - mid);
        add[o] = 0;
    }
    if(tag[o] != -1) {
        tag[lch] = tag[rch] = tag[o];
        sum[lch] = val[lch] * tag[o];
        sum[rch] = val[rch] * tag[o];
        tag[o] = -1;
    }
}

inline void modify(int o, int l, int r, int ll, int rr, int v) {
    if(l >= ll && r <= rr) {
        val[o] += v * (r - l + 1);
        add[o] += v;
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(ll <= mid) modify(lch, l, mid, ll, rr, v);
    if(rr > mid) modify(rch, mid + 1, r, ll, rr, v);
    val[o] = val[lch] + val[rch];
}

inline void select(int o, int l, int r, int ll, int rr, int v) {
    if(l >= ll && r <= rr) {
        sum[o] = val[o] * v;
        tag[o] = v;
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(ll <= mid) select(lch, l, mid, ll, rr, v);
    if(rr > mid) select(rch, mid + 1, r, ll, rr, v);
    sum[o] = sum[lch] + sum[rch];
}

inline void modify(int u, int v, int x) {
    int tu = top[u], tv = top[v];
    while(tu != tv) {
        if(dep[tu] > dep[tv]) {
            std::swap(u, v);
            std::swap(tu, tv);
        }
        modify(1, 1, n, dfn[tv], dfn[v], x);
        v = fa[tv];
        tv = top[v];
    }
    if(dep[u] > dep[v]) std::swap(u, v);
    modify(1, 1, n, dfn[u], dfn[v], x);
}

inline void select(int u, int v) {
    int tu = top[u], tv = top[v];
    while(tu != tv) {
        if(dep[tu] > dep[tv]) {
            std::swap(u, v);
            std::swap(tu, tv);
        }
        select(1, 1, n, dfn[tv], dfn[v], 1);
        v = fa[tv];
        tv = top[v];
    }
    if(dep[u] > dep[v]) std::swap(u, v);
    select(1, 1, n, dfn[u], dfn[v], 1);
}

int main() {
    n = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt);
    }
    dfs1(1);
    dfs2(1, 1);
    q = readint();
    while(q--) {
        op = readint();
        if(op == 0) {
            ut = readint(); xt = readint();
            modify(1, 1, n, dfn[ut], dfn[ut] + siz[ut], xt);
        } else {
            kt = readint();
            while(kt--) {
                ut = readint(); vt = readint();
                select(ut, vt);
            }
            printf("%d\n", sum[1] & 2147483647);
            select(1, 1, n, 1, n, 0);
        }
    }
    return 0;
}