题面
题目传送门(HDU 6962 I love tree)
Given a tree with n nodes and q operations, there are two kinds of operations.
1 a b : for a chain <a, b>, increase the value of x2 to the x-th point on this chain
for example the chain from a to b=(x1,x2,x3,x4,x5),after the operation,x1+=1,x2+=4,x3+=9,x4+=16,x5+=25
2 x :asks the value of x-th node
翻译：两种操作
1：一棵无根树，在节点
x
x
x
到节点
y
y
y
的最近链上，从
x
x
x
开始，每次加
i
2
(
1
<
=
i
<
=
l
e
n
)
i^2(1<=i<=len)
i
2
(
1
<
=
i
<
=
l
e
n
)
l
e
n
len
l
e
n
为链的长度
2：查询节点
x
x
x
的值是多少
很容易想到
树链剖分+线段树
难点在于
如何维护区间加平方
树链剖分这一块接下来细说，现在考虑如何维护
a
L
+
1
2
,
a
L
+
i
+
2
2
,
a
R
+
(
R
−
L
+
1
)
2
a_L+1^2,a_{L+i}+2^2,a_{R}+(R-L+1)^2
a
L
+
1
2
,
a
L
+
i
+
2
2
,
a
R
+
(
R
−
L
+
1
)
2
考虑对区间
[
L
,
R
]
[L, R]
[
L
,
R
]
进行上面的操作
第一个数加1的平方，第二个数加2的平方，以此类推
发现，加1和加2的平方都是由，当前位置
i
i
i
和起始操作位置
l
l
l
决定的
为了方便讨论令
l
=
L
−
1
l = L-1
l
=
L
−
1
(其实就是为了好分析加的是多少的平方)
也就是对于
a
i
a_i
a
i
来说，
a
i
+
(
i
−
l
)
2
a_i+(i-l)^2
a
i
+
(
i
−
l
)
2
a
i
a_i
a
i
初始为0，对后面的式子进行分解
(
i
−
l
)
2
=
i
2
+
l
2
−
2
∗
i
∗
l
(i-l)^2 = i^2 +l^2-2*i*l
(
i
−
l
)
2
=
i
2
+
l
2
−
2
∗
i
∗
l
假如我们要求某一个点
a
i
a_i
a
i
的值
此时会等于
a
i
+
∑
i
2
+
∑
l
2
−
∑
2
∗
i
∗
l
a_i + \sum{i^2} + \sum{l^2} -\sum{2*i*l}
a
i
+
∑
i
2
+
∑
l
2
−
∑
2
∗
i
∗
l
由于
a
i
a_i
a
i
初始为0，
i
2
i^2
i
2
和
2
∗
i
2*i
2
∗
i
也已知，从求和公式提出
最后变为了
i
2
∗
∑
1
+
∑
l
2
−
2
∗
i
∗
∑
l
i^2*\sum{1} + \sum{l^2} -2*i*\sum{l}
i
2
∗
∑
1
+
∑
l
2
−
2
∗
i
∗
∑
l
从而分析，通过线段树或者树状数组维护，每个
i
i
i
的这三个求和的值，也就是区间和
另外由上面公式推及，
l
=
L
−
1
l=L-1
l
=
L
−
1
，区间
[
L
,
R
]
[L,R]
[
L
,
R
]
加平方(顺序加，如1，4，9，16)，就要在区间
[
L
,
R
]
[L,R]
[
L
,
R
]
维护
∑
1
,
∑
(
L
−
1
)
2
,
∑
L
−
1
\sum{1},\sum{(L-1)^2,\sum{L-1}}
∑
1
,
∑
(
L
−
1
)
2
,
∑
L
−
1
问题
假如要倒着加呢如(16, 9, 4, 1)
同样考虑区间
[
L
,
R
]
[L,R]
[
L
,
R
]
a
i
+
(
R
−
i
+
1
)
2
a_i+(R-i+1)^2
a
i
+
(
R
−
i
+
1
)
2
，令
r
=
R
+
1
r=R+1
r
=
R
+
1
(
r
−
i
)
2
=
(
i
−
r
)
2
(r-i)^2=(i-r)^2
(
r
−
i
)
2
=
(
i
−
r
)
2
这样又能由上面的过程推到答案了
也就是说，倒着加就让参数
l
l
l
变为
r
r
r
即可实现，复用同一个线段树
树链剖分
我们知道树链剖分的
t
o
p
[
u
]
top[u]
t
o
p
[
u
]
到
u
u
u
是
d
f
n
dfn
d
f
n
连续的一段，可以使用线段树进行维护
类似于找lca的过程，过程中仔细考虑一下，此过程是顺得加，还是倒着加，时刻记录顺的加了多少，倒着加了多少的左右端点为
l
l
l
和
r
r
r
那么加多少呢?
下面
s
t
,
e
d
,
L
,
R
st,ed,L,R
s
t
,
e
d
,
L
,
R
的定义不同
在一条
树剖链
a
a
a
~
b
b
b
上（意味着
d
f
n
dfn
d
f
n
连续，线段树维护的就是这一段连续的区间）执行从
L
2
L^2
L
2
加到
R
2
R^2
R
2
。
-
从
aa
a
~
bb
b
，
de
p
[
a
]
<
d
e
p
[
b
]
dep[a] < dep[b]
d
e
p
[
a
]
<
d
e
p
[
b
]
的情况
对于每个
ii
i
，加的值是
(s
t
+
i
)
2
(st+i)^2
(
s
t
+
i
)
2
考虑
aa
a
~
bb
b
间的某个点
xx
x
我们计算的
i=
d
f
n
[
x
]
−
d
f
n
[
a
]
+
1
i = dfn[x] – dfn[a]+1
i
=
d
f
n
[
x
]
−
d
f
n
[
a
]
+
1
，也就是段落第几个数
起始加的值
st
=
R
−
l
e
n
(
a
,
b
)
st = R-len(a,b)
s
t
=
R
−
l
e
n
(
a
,
b
)
带入公式中能够推到
(R
−
l
e
n
+
d
f
n
[
x
]
−
d
f
n
[
a
]
+
1
)
2
(R-len+dfn[x] – dfn[a] + 1)^2
(
R
−
l
e
n
+
d
f
n
[
x
]
−
d
f
n
[
a
]
+
1
)
2
进一步化为
(d
f
n
[
x
]
−
(
d
f
n
[
a
]
−
(
R
−
l
e
n
+
1
)
)
)
2
(dfn[x] – (dfn[a] – (R-len+1)))^2
(
d
f
n
[
x
]
−
(
d
f
n
[
a
]
−
(
R
−
l
e
n
+
1
)
)
)
2
上面为
什么要
化成这种形式呢？因为后面计算用到的是
an
s
=
s
1
∗
d
f
n
[
x
]
2
+
s
2
−
2
∗
d
f
n
[
x
]
∗
s
3
ans = s1*dfn[x]^2 + s2 – 2*dfn[x]*s3
a
n
s
=
s
1
∗
d
f
n
[
x
]
2
+
s
2
−
2
∗
d
f
n
[
x
]
∗
s
3
我们得在区间维护一个针对
df
n
[
x
]
dfn[x]
d
f
n
[
x
]
的二次函数，
(x
−
b
)
2
(x-b)^2
(
x
−
b
)
2
形式，这里可以和上面线段树的知识对应起来 -
从
bb
b
~
aa
a
，
de
p
[
a
]
<
d
e
p
[
c
]
dep[a] < dep[c]
d
e
p
[
a
]
<
d
e
p
[
c
]
的情况(
aa
a
~
bb
b
的
df
n
dfn
d
f
n
连续增)
对于每个i，加的值是
(e
d
−
i
)
2
(ed-i)^2
(
e
d
−
i
)
2
考虑
aa
a
~
bb
b
的某个点x，对应的
i=
d
f
n
[
x
]
−
d
f
n
[
a
]
+
1
i = dfn[x] – dfn[a] + 1
i
=
d
f
n
[
x
]
−
d
f
n
[
a
]
+
1
，从
aa
a
到
bb
b
第几个数
bb
b
~
aa
a
最后一个加的值
ed
=
L
+
l
e
n
(
a
,
b
)
ed = L + len(a, b)
e
d
=
L
+
l
e
n
(
a
,
b
)
带入公式种能够推到
(e
d
+
d
f
n
[
a
]
−
d
f
n
[
x
]
−
1
)
2
(ed + dfn[a] – dfn[x] – 1)^2
(
e
d
+
d
f
n
[
a
]
−
d
f
n
[
x
]
−
1
)
2
进一步化为
((
d
f
n
[
a
]
+
(
L
+
l
e
n
−
1
)
)
−
d
f
n
[
x
]
)
2
((dfn[a]+(L+len-1))-dfn[x])^2
(
(
d
f
n
[
a
]
+
(
L
+
l
e
n
−
1
)
)
−
d
f
n
[
x
]
)
2
也会等于
(d
f
n
[
x
]
−
(
d
f
n
[
a
]
+
(
L
+
l
e
n
+
1
)
)
)
2
(dfn[x]-(dfn[a]+(L+len+1)))^2
(
d
f
n
[
x
]
−
(
d
f
n
[
a
]
+
(
L
+
l
e
n
+
1
)
)
)
2
综上
通过维护形如
(
x
−
b
)
2
(x-b)^2
(
x
−
b
)
2
的二次函数，也就是维护其中关于的三个系数，就能维护正的加平方和倒着加平方的值
树链剖分，对于每一个链
(
t
o
p
[
a
]
,
a
)
(top[a],a)
(
t
o
p
[
a
]
,
a
)
，如果是从
x
x
x
加到
y
y
y
方向的，则按第一种方法正的加，起始加的值
s
t
st
s
t
是每次加完跟新后的值，区间长度
l
e
n
=
d
e
p
[
a
]
−
d
e
p
[
t
o
p
[
a
]
]
+
1
len = dep[a] – dep[top[a]]+1
l
e
n
=
d
e
p
[
a
]
−
d
e
p
[
t
o
p
[
a
]
]
+
1
，如果是反方向就第二种加法，取法相同不多赘述
下面详细代码
//6962
/*
@Author: YooQ
*/
#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define ll long long
#define int long long
#define FILE_OUT freopen("out", "w", stdout);
#define FILE_IN freopen("in", "r", stdin);
#define debug(x) cout << #x << ": " << x << "\n";
#define AC 0
#define WA 1
#define INF 0x3f3f3f3f
const ll MAX_N = 2e6+5;
const ll MOD = 1e9+7;
int N, M, K;
struct Seg{
struct Tr{
int k;
int lazy;
}tr[MAX_N];
void push_up(int rt) {
tr[rt].k = tr[rt<<1].k + tr[rt<<1|1].k;
}
void calc(int rt, int len, int add) {
tr[rt].k += len * add;
tr[rt].lazy += add;
}
void push_down(int rt, int l, int r) {
int lc = rt<<1;
int rc = rt<<1|1;
int mid = l + ((r-l)>>1);
calc(lc, mid - l + 1, tr[rt].lazy);
calc(rc, r - mid, tr[rt].lazy);
tr[rt].lazy = 0;
}
void build(int rt, int l, int r) {
tr[rt].k = 0;
tr[rt].lazy = 0;
if (l == r) return;
int mid = l + ((r-l)>>1);
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
push_up(rt);
}
void update(int rt, int l, int r, int x, int y, int k) {
if (x <= l && r <= y) {
calc(rt, r-l+1, k);
return;
}
push_down(rt, l, r);
int mid = l + ((r-l)>>1);
if (x <= mid) update(rt<<1, l, mid, x, y, k);
if (y > mid) update(rt<<1|1, mid+1, r, x, y, k);
push_up(rt);
}
int query(int rt, int l, int r, int x) {
if (l == r) {
return tr[rt].k;
}
push_down(rt, l, r);
int mid = l + ((r-l)>>1);
if (x <= mid) return query(rt<<1, l, mid, x);
if (x > mid) return query(rt<<1|1, mid+1, r, x);
}
}s1, s2, s3;
int head[MAX_N];
int tot = 0;
struct Edge{
int to, nxt;
}edge[MAX_N];
void addEdge(int u, int v) {
edge[tot].nxt = head[u];
edge[tot].to = v;
head[u] = tot++;
edge[tot].nxt = head[v];
edge[tot].to = u;
head[v] = tot++;
}
int rk[MAX_N];
int indx = 0;
int dfn[MAX_N];
int son[MAX_N];
int sz[MAX_N];
int father[MAX_N];
int dep[MAX_N];
int top[MAX_N];
void dfs1(int u, int from, int d) {
dep[u] = d;
father[u] = from;
sz[u] = 1;
son[u] = 0;
int v;
for (int i = head[u];~i;i=edge[i].nxt) {
if ((v=edge[i].to) == from) continue;
dfs1(v, u, d+1);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) {
son[u] = v;
}
}
}
void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++indx;
rk[indx] = u;
if (!son[u]) return;
dfs2(son[u], tp);
int v;
for (int i = head[u];~i;i=edge[i].nxt) {
if ((v=edge[i].to) == son[u] || v == father[u]) continue;
dfs2(v, v);
}
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] >= dep[top[y]]) {
x = father[top[x]];
} else {
y = father[top[y]];
}
}
return dep[x] < dep[y] ? x : y;
}
void change(int x, int y) {
int lca = LCA(x, y);
int l = 1, r = dep[x] + dep[y] - 2 * dep[lca] + 1;
int add = 0, len = 0;
while (top[x] != top[y]) {
if (dep[top[x]] >= dep[top[y]]) {
len = dep[x] - dep[top[x]] + 1;
l += len;
add = dfn[top[x]] + (l - 1);
s1.update(1, 1, N, dfn[top[x]], dfn[x], 1);
s2.update(1, 1, N, dfn[top[x]], dfn[x], add * add);
s3.update(1, 1, N, dfn[top[x]], dfn[x], add);
x = father[top[x]];
} else {
len = dep[y] - dep[top[y]] + 1;
r -= len;
add = dfn[top[y]] - (r + 1);
s1.update(1, 1, N, dfn[top[y]], dfn[y], 1);
s2.update(1, 1, N, dfn[top[y]], dfn[y], add * add);
s3.update(1, 1, N, dfn[top[y]], dfn[y], add);
y = father[top[y]];
}
}
if (dep[x] > dep[y]) {
len = dep[x] - dep[y] + 1;
l += len;
add = dfn[y] + (l - 1);
s1.update(1, 1, N, dfn[y], dfn[x], 1);
s2.update(1, 1, N, dfn[y], dfn[x], add * add);
s3.update(1, 1, N, dfn[y], dfn[x], add);
} else {
len = dep[y] - dep[x] + 1;
r -= len;
add = dfn[x] - (r + 1);
s1.update(1, 1, N, dfn[x], dfn[y], 1);
s2.update(1, 1, N, dfn[x], dfn[y], add * add);
s3.update(1, 1, N, dfn[x], dfn[y], add);
}
}
void init() {
memset(head, -1, sizeof head);
tot = 0;
indx = 0;
}
void solve(){
init();
sc("%lld", &N);
int u, v, w;
for (int i = 1; i < N; ++i) {
sc("%lld%lld", &u, &v);
addEdge(u, v);
}
dfs1(1, 0, 1);dfs2(1, 1);
sc("%lld", &M);
int opt, a, b, x;
s1.build(1, 1, N);s2.build(1, 1, N);s3.build(1, 1, N);
for (int i = 1; i <= M; ++i) {
sc("%lld", &opt);
if (opt == 1) {
sc("%lld%lld", &a, &b);
change(a, b);
} else {
sc("%lld", &x);
int ans = s1.query(1, 1, N, dfn[x]) * dfn[x] * dfn[x] + s2.query(1, 1, N, dfn[x]) - 2 * dfn[x] * s3.query(1, 1, N, dfn[x]);
pr("%lld\n", ans);
}
}
}
signed main()
{
#ifndef ONLINE_JUDGE
// FILE_IN
FILE_OUT
#endif
int T = 1;//cin >> T;
while (T--) solve();
return AC;
}