【题目描述】
在暑假来临之际，小 Z 的地理老师布置了一个暑假作业，让同学们暑假期间 了解一下 C 国的铁路发展史。小 Z 在多番查证资料后发现，C 国在铁路发展初期， 铁路网络有着一个严密规整的结构：C 国的 N 个城市按层级分为首都、省会、省 辖市……由于在铁路发展初期，建造铁路花费巨大，为了避免不必要的浪费，铁 路网络的建设保证了任意两个城市相互连通，且仅有一条连通路径。 随后，小 Z 还查阅到历年来铁道部向全国上下发布的大小消息。由于多年来 C 国货币系统保持健康的 3%通胀率带来了稳定的物价上涨，铁道部发布的消息中 不乏对某段连接城市 u 与城市 v 铁路的价格上涨 w 元的通知。于是小 Z 不禁好奇， 在某些特定时间，在某个城市 p 的管辖区域内，任意两个城市间的铁路通勤的费 用和是多少。
【输入格式】
第一行输入两个正整数 N，Q，分别表示城市的数目和操作的数目。 接下来有 N–1 行，第 i 行是两个正整数 p[i], c[i]，表示城市 p[i]是城市 i 的父亲结点，且连接 p[i]和 i 的铁路的初始收费为 c[i]（1≤c[i]≤1000）。 再接下来有 Q 行，每行是如下两种类型之一： INC u v w (u, v, w 都是整数，且 1≤u, v≤N, 0≤w≤1000) ASK p (p 是整数，且 0≤p≤N) 意义如题目所述。
【输出格式】
对每个 ASK 类型的操作，输出所求的答案。请你输出答案对 2019 取模后的 结果。
【样例输入】
5 5
1 1
2 5
1 2
2 1
INC 2 4 2
INC 3 4 1
ASK 2
INC 2 5 3
ASK 1
【样例输出】
14 84
思路：
题目大意：给你一棵有根树，每条边有边权。实现两种操作：
1.给某一条路径上所 有边的权值加上一个数；
2.询问某棵子树内所有点对的距离和。 本题设置了几个部分分梯度，得部分分的做法有不少， 复杂度也各有千秋。下面给出比较容易理解的一种满分解 法。
从查询的角度思考，如何计算以 i 为根的子树内所有点 对的距离和？
不妨设点 x 与它的父亲 fa[x]相连的边的权值为 p[x]，考虑 p[x]会对那些点对产生贡 献？显然是经过 x——fa[x]这条边的那些点对。
记 siz[x]为以 x 为根的子树的大小。则经过 x——fa[x]的点对有 siz[x]×(siz[i] – siz[x])对（如图 5），
于是，子树 i 内的点 x 的贡献就是 p[x]×siz[x]×siz[i] – p[x]×(siz[x])²。黄色的部分与 i 无关。
如果要计算，我们只需把子树 i 内所有点（不包括 i）的自己的黄色部分加起来，然后就可以求出答案。
这是因为 ∑(p[x]×siz[x]×siz[i] – p[x]×(siz[x])²) = siz[i]×∑(p[x]×siz[x]) – ∑(p[x]×(siz[x])²) 而修改操作，就是给一条路径上所有点（准确地说，不含 LCA）的 p 加上一个数。
我们要高效地维护上面黄色部分标出的两种“和”。这里有两种解法：
解法一
：
树链剖分 + DFS 序。 修改操作在树的链上进行，可以考虑使用树链剖分；而查询操作是查询子树的和，可 以考虑用 DFS 序。 树链剖分，把重链的结点在线段树中连续存放； 而 DFS 序，把子树结点连续存放。
两者可以兼得吗？ 事实上，进行树链剖分的时候，我们 记 录了每个结点的“重儿子”，求树的 DFS 序 时， 我们对每个结点都先搜索它的重儿子再搜 索 其他儿子。
这样，就可以保证，DFS 序中， 每 条重链是连续存放的，每棵子树也是连续 存 放的，可以使用同一棵线段树存放。（不 妨 参考如图 6 的例子）
在线段树中，很容易 处 理让一段的值都加上一个数和查询一段的 和 这样的操作。 这样做是 O(n (log2n) 2)的。
代码：
#include<bits/stdc++.h>
typedef long long LL;
const int N = 100000;
const int M = 5000;
const int inf = 2147483647;
const int p = 2019;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline void _(char ch){*O++ = ch;}
void print(int x) {if(x < 0) _('-'), x = -x; if(x>9) print(x/10);*O++ = x % 10 ^ 48;}
inline int read(){
int res = 0; char ch = getchar(); bool bo = false;
while(ch < '0' || ch > '9') bo = (ch == '-'), ch = getchar();
while(ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
return bo ? -res : res;
}
int getc() {
char ch = getchar();
while(ch != 'A' && ch != 'I') ch = getchar();
return ch == 'I';
}
struct Edge {
int to;
Edge *nxt;
Edge (int to, Edge *nxt) : to(to), nxt(nxt) {}
}*head[N];
int dep[N], a[N], size[N], siz[N], son[N], Top[N], fa[N], dfn[N], nfd[N], tot;
struct Segment {
struct node {
int sum, tag, siz;
int l, r;
node *L, *R;
node(int l, int r) : sum(0), tag(0), siz(0), l(l), r(r), L(NULL), R(NULL) {}
void up() {
siz = (L->siz + R->siz) % p;
sum = (L->sum + R->sum) % p;
}
void down() {
L->sum = (L->sum + L->siz * tag) % p;
R->sum = (R->sum + R->siz * tag) % p;
L->tag = (L->tag + tag) % p; R->tag = (R->tag + tag) % p;
tag = 0;
}
int mid() {return (l + r) >> 1;}
}*root;
void bulid(node *&o, int l, int r, bool bo) {
o = new node(l, r);
if(l == r) {
int Siz = siz[nfd[l]] % p;
if(bo) Siz = ((LL)Siz * siz[nfd[l]]) % p;
o->siz = Siz;
o->sum = (Siz * a[nfd[l]]) % p;
return;
}
bulid(o->L, l, o->mid(), bo);
bulid(o->R, o->mid() + 1, r, bo);
o->up();
}
void chenge(node *o, int l, int r, int tag) {
if(o->l >= l && o->r <= r) {
o->sum = (o->sum + o->siz * tag) % p;
o->tag = (o->tag + tag) % p;
return;
}
if(o->tag) o->down();
if(o->mid() >= l) chenge(o->L, l, r, tag);
if(o->mid() < r) chenge(o->R, l, r, tag);
o->up();
}
int ask(node *o, int l, int r) {
if(o->l >= l && o->r <= r) return o->sum;
if(o->tag) o->down();
int ans = 0;
if(o->mid() >= l) ans += ask(o->L, l, r);
if(o->mid() < r) ans += ask(o->R, l, r);
return ans % p;
}
}wfx, cdy;
void dfs(int x, int f) {
dep[x] = dep[fa[x] = f] + (siz[x] = 1);
for(Edge *i = head[x]; i; i = i->nxt) {
if(i->to == f) continue;
dfs(i->to, x);
siz[x] += siz[i->to];
if(siz[i->to] > siz[son[x]]) son[x] = i->to;
}
}
void dfs(int x, int f, int top) {
Top[nfd[dfn[x] = ++tot] = x] = top;
if(son[x]) dfs(son[x], x, top);
for(Edge *i = head[x]; i; i = i->nxt) {
if(i->to == son[x] || i->to == f) continue;
dfs(i->to, x, i->to);
}
}
void chenge(int x, int y, int d) {
if(x == y) return;
while(Top[x] != Top[y]) {
if(dep[Top[x]] < dep[Top[y]]) std::swap(x, y);
wfx.chenge(wfx.root, dfn[Top[x]], dfn[x], d);
cdy.chenge(cdy.root, dfn[Top[x]], dfn[x], d);
x = fa[Top[x]];
}
if(x == y) return;
if(dep[x] > dep[y]) std::swap(x, y);
wfx.chenge(wfx.root, dfn[x] + 1, dfn[y], d), cdy.chenge(cdy.root, dfn[x] + 1, dfn[y], d);
}
int ask(int k) {
if(siz[k] <= 1) return 0;
int a = wfx.ask(wfx.root, dfn[k] + 1, dfn[k] + siz[k] - 1), b = cdy.ask(cdy.root, dfn[k] + 1, dfn[k] + siz[k] - 1);
return ((siz[k] * a - b) % p + p) % p;
}
int main()
{
#ifdef yilnr
#else
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
#endif
int n = read(), m = read();
for(int i = 2; i <= n; ++i) {
int x = read(); a[i] = read();
head[x] = new Edge (i, head[x]);
}
dfs(1, 0);
dfs(1, 0, 1);
wfx.bulid(wfx.root, 1, n, false);
cdy.bulid(cdy.root, 1, n, true);
for(; m --> 0; ) {
int opt = getc(), l, r, d;
if(opt) l = read(), r = read(), d = read(), chenge(l, r, d);
else printf("%d
", ask(read()));
}
return 0;
}