传送
话说还挺喜欢多校这风格，题面干净利落，没有废话。
这题一看就是树剖+线段树，但就是没想明白咋维护。
遇到这种情况，先想想序列上怎么办：给([L,R])依次加上(1^2，2^2,cdots,(R-L+1)^2)，怎么维护？之所以不好维护，是因为不同操作给同一区间打的“标记的性质”不一样，使其无法下传。这个“标记的性质”，就比如都是加一个定值，那就是相同的性质，但这道题是加的数随着开始的位置不同而不同。
那么能否统一呢？只要想办法将相对位置转换成绝对位置就好了。
对于([L,R])中的第(x)个数(a_i)，加的(x^2=(i-L+1)^2)，展开后有(i^2-2(L-1)i+(L-1)^2)，这时会发现这三部分全是静态的标记，就可以用线段树分别维护了。
序列会了，换到了树上，大同小异，只不过复杂了一些：
1.一条路径对应着线段树上若干个区间，这时每个区间的第一个数就不再是加1了，而是要自己算出来，再用上面的公式维护。
2.树上的路径有方向，在线段树上的区间就有分别加递增和递减两个序列之分，二次函数展开后只是在第二项差一个正负号，但要在树剖跳重链的时候要单独考虑。
3.我比较憨，用的线段树，题解直接树状数组了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m;
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
int dep[maxn], fa[maxn], siz[maxn], son[maxn];
In void dfs1(int now, int _f)
{
siz[now] = 1;
forE(i, now, v)
{
if(v == _f) continue;
dep[v] = dep[now] + 1, fa[v] = now;
dfs1(v, now);
siz[now] += siz[v];
if(!son[now] || siz[v] > siz[son[now]]) son[now] = v;
}
}
int top[maxn], dfsx[maxn], pos[maxn], cnt = 0;
In void dfs2(int now, int _f)
{
dfsx[now] = ++cnt, pos[cnt] = now;
if(son[now]) top[son[now]] = top[now], dfs2(son[now], now);
forE(i, now, v) if(v != _f && v != son[now]) top[v] = v, dfs2(v, now);
}
In int lca(int x, int y)
{
while(top[x] ^ top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
ll S1[maxn], S2[maxn];
struct Tree
{
int l, r;
ll sum1, sum2, sum3;
ll lzy1, lzy2, lzy3;
In void change(ll l1, ll l2, ll l3)
{
lzy1 += l1, sum1 += l1 * (r - l + 1);
lzy2 += l2, sum2 += l2 * (S1[r] - S1[l - 1]);
lzy3 += l3, sum3 += l3 * (S2[r] - S2[l - 1]);
}
}t[maxn << 2];
In void build(int L, int R, int now)
{
t[now].l = L, t[now].r = R;
if(L == R) return;
int mid = (L + R) >> 1;
build(L, mid, now << 1), build(mid + 1, R, now << 1 | 1);
}
In void pushdown(int now)
{
if(t[now].lzy3)
{
t[now << 1].change(t[now].lzy1, t[now].lzy2, t[now].lzy3);
t[now << 1 | 1].change(t[now].lzy1, t[now].lzy2, t[now].lzy3);
t[now].lzy1 = t[now].lzy2 = t[now].lzy3 = 0;
}
}
In void update(int L, int R, int now, ll d, int flg)
{
if(t[now].l == L && t[now].r == R)
{
t[now].change(d * d, (d << 1) * flg, 1);
return;
}
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(R <= mid) update(L, R, now << 1, d, flg);
else if(L > mid) update(L, R, now << 1 | 1, d, flg);
else update(L, mid, now << 1, d, flg), update(mid + 1, R, now << 1 | 1, d, flg);
t[now].sum1 = t[now << 1].sum1 + t[now << 1 | 1].sum1;
t[now].sum2 = t[now << 1].sum2 + t[now << 1 | 1].sum2;
t[now].sum3 = t[now << 1].sum3 + t[now << 1 | 1].sum3;
}
In ll query(int now, int x)
{
if(t[now].l == t[now].r) return t[now].sum1 + t[now].sum2 + t[now].sum3;
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(x <= mid) return query(now << 1, x);
else return query(now << 1 | 1, x);
}
In void update_path(int x, int y)
{
int f1 = 1, f2 = dep[x] + dep[y] - (dep[lca(x, y)] << 1) + 1;
while(top[x] ^ top[y])
{
if(dep[top[x]] > dep[top[y]])
{
f1 += dep[x] - dep[top[x]];
update(dfsx[top[x]], dfsx[x], 1, f1 + dfsx[top[x]], -1);
x = fa[top[x]], f1++;
}
else
{
f2 -= dep[y] - dep[top[y]];
update(dfsx[top[y]], dfsx[y], 1, f2 - dfsx[top[y]], 1);
y = fa[top[y]], f2--;
}
}
if(dep[x] < dep[y]) update(dfsx[x], dfsx[y], 1, f1 - dfsx[x], 1);
else update(dfsx[y], dfsx[x], 1, f2 + dfsx[y], -1);
}
int main()
{
// MYFILE();
Mem(head, -1), ecnt = -1;
n = read();
for(int i = 1; i <= n; ++i) S1[i] = S1[i - 1] + i, S2[i] = S2[i - 1] + 1LL * i * i;
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
addEdge(x, y), addEdge(y, x);
}
dep[1] = 1, dfs1(1, 0);
top[1] = 1, dfs2(1, 0);
build(1, n, 1);
m = read();
for(int i = 1; i <= m; ++i)
{
int op = read(), x = read();
if(op == 1)
{
int y = read();
update_path(x, y);
}
else write(query(1, dfsx[x])), enter;
}
return 0;
}