题目大意
给你一颗树，有两种操作。一种是给树上两个点之间的点((x_1, x_2...x_k))加上(1^2, 2^2...k^2)。另一种是查询树上某个节点的值，初始每个节点的值都是(0)。
解题思路
题目很明显可以树剖之后建线段树来做区间修改和单点查询。 给区间加上等差数列的平方可以用加二次函数的形式。对于区间([l,r])，设(k=l-1)，可以对每个数加上((i-k)^2)，(i)是这个元素的下标，但是这样不具有可加性，可以试着把式子展开，变成(i^2-2ki+k^2)，将(i)提出来，变成(i^2 imes 1 - 2i imes k + k^2)，我们发现(1)，(k)，(k^2)是可以累加的，用线段树分别维护区间内三种数的和即可。
由于树剖之后两个结点会同时往上跳，就有了要计算正着加和倒着加的情况，倒着加也很简单，设(k)等于(r+1)，就变成了对每个数加((k-i)^2)，翻转一下变成(i-k)，发现和前面只是(k)的取值不同罢了。
const int maxn = 2e5+10;
const int maxm = 1e7+10;
int n, q;
vector<int> e[maxn];
int dep[maxn], fa[maxn], sz[maxn], son[maxn];
void dfs1(int u, int p) {
sz[u] = 1;
for (auto v : e[u]) {
if (v==p) continue;
dep[v] = dep[u]+1;
fa[v] = u;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v]>sz[son[u]]) son[u] = v;
}
}
int top[maxn], tim, id[maxn], rev[maxn];
void dfs2(int u, int t) {
top[u] = t;
id[u] = ++tim;
rev[tim] = u;
if (!son[u]) return;
dfs2(son[u], t);
for (auto v : e[u])
if (v!=fa[u] && v!=son[u]) dfs2(v, v);
}
struct Node {
ll lz1, lz2, lz3;
} tr[maxn<<2];
inline void push_down(int rt) {
if (tr[rt].lz1) {
Node &f = tr[rt];
Node &ls = tr[rt<<1];
Node &rs = tr[rt<<1|1];
ls.lz1 += f.lz1;
ls.lz2 += f.lz2;
ls.lz3 += f.lz3;
rs.lz1 += f.lz1;
rs.lz2 += f.lz2;
rs.lz3 += f.lz3;
f.lz1 = f.lz2 = f.lz3 = 0;
}
}
void update(int rt, int l, int r, int L, int R, ll val) {
if (l>=L && r<=R) {
tr[rt].lz1 += 1;
tr[rt].lz2 += val*val;
tr[rt].lz3 += val;
return;
}
push_down(rt);
int mid = (l+r)>>1;
if (L<=mid) update(rt<<1, l, mid, L, R, val);
if (R>mid) update(rt<<1|1, mid+1, r, L, R, val);
}
Node ask(int rt, int l, int r, int pos) {
if (l==r) return tr[rt];
push_down(rt);
int mid = (l+r)>>1;
if (pos<=mid) return ask(rt<<1, l, mid, pos);
else return ask(rt<<1|1, mid+1, r, pos);
}
int lca(int u, int v) {
while(top[u]!=top[v]) {
if (dep[top[u]]>dep[top[v]]) u = fa[top[u]];
else v = fa[top[v]];
}
return dep[u]>dep[v] ? v:u;
}
void modify(int u, int v) {
int l = 1, r = dep[u]+dep[v]-2*dep[lca(u, v)]+1;
int add = 0;
while(top[u]!=top[v]) {
if (dep[top[u]]>dep[top[v]]) { //u往上跳，从top[u]到u倒着加
add = id[u]+l;
l += id[u]-id[top[u]];
update(1, 1, n, id[top[u]], id[u], add);
u = fa[top[u]];
++l;
}
else { //v往上跳从top[v]到v正着加
r -= dep[v]-dep[top[v]];
add = id[top[v]]-r;
update(1, 1, n, id[top[v]], id[v], add);
v = fa[top[v]];
--r;
}
}
if (dep[u]>dep[v]) {
add = id[u]+l;
update(1, 1, n, id[v], id[u], add);
}
else {
add = id[u]-l;
update(1, 1, n, id[u], id[v], add);
}
}
int main() {
IOS;
cin >> n;
for (int i = 1, a, b; i<n; ++i) {
cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
dfs1(1, 0); dfs2(1, 1);
cin >> q;
while(q--) {
int o, l, r; cin >> o;
if (o==1) {
cin >> l >> r;
modify(l, r);
}
else if (o==2) {
cin >> l;
Node res = ask(1, 1, n, id[l]);
ll ans = id[l]*id[l]*res.lz1+res.lz2-2*id[l]*res.lz3;
cout << ans << endl;
}
}
return 0;
}