树链剖分
对树上的一条链加\(1^2,2^2,...n^2\)。
每次询问单点。
我们设L是u和v的LCA。
那么对于链u->L，区间加上\((dep_u-dep_x+1)^2\)。
即加上\((dep_x-dep_u-1)^2\)
对于链L->v，区间加上\((dep_u-dep_L+1+dep_x-dep_L)^2\)
即\((dep_x-(2dep_L-dep_u-1))^2\)
这两步式子化出来之后，我们发现，就是对\(i \in [L,R]\)增加
\((a_i-x)^2=(a_i^2-2xa_i+x^2)\)
对于每次修改，区间内的x都是一样的。
对于式子的第一项，我们只需要维护每个位置\(a_i^2\)的个数即可，区间+1。
对于式子的第二项，我们需要维护\(a_i\)的个数，区间减2x即可。
对于式子的第三项，我们只需要区间\(+x^2\)即可。
这三项分别开S1 S2 S3三颗线段树维护即可。
最后答案就是S1的答案乘\(a_i^2\)，S2的答案乘\(a_i\)，S3的答案，求和即可。
时间复杂度\(O(nlognlogn)\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int M=3e6+100;
typedef long long ll;
ll c[M],lz[M],lson[M],rson[M],tot,T[4];
int build (int l,int r) {
int newRoot=++tot;
c[newRoot]=lz[newRoot]=0;
if (l==r) {
return newRoot;
}
int mid=(l+r)>>1;
lson[newRoot]=build(l,mid);
rson[newRoot]=build(mid+1,r);
return newRoot;
}
void pushdown (int u,int l,int r) {
if (lz[u]) {
int mid=(l+r)>>1;
c[lson[u]]+=1ll*(mid-l+1)*lz[u];
lz[lson[u]]+=lz[u];
c[rson[u]]+=1ll*(r-mid)*lz[u];
lz[rson[u]]+=lz[u];
lz[u]=0;
}
}
void up (int u,int l,int r,int L,int R,ll v) {
if (l>=L&&r<=R) {
c[u]+=1ll*(r-l+1)*v;
lz[u]+=v;
return;
}
pushdown(u,l,r);
int mid=(l+r)>>1;
if (L<=mid) up(lson[u],l,mid,L,R,v);
if (R>mid) up(rson[u],mid+1,r,L,R,v);
c[u]=c[lson[u]]+c[rson[u]];
}
ll query (int u,int l,int r,int L,int R) {
if (l>=L&&r<=R) return c[u];
pushdown(u,l,r);
int mid=(l+r)>>1;
ll ans=0;
if (L<=mid) ans+=query(lson[u],l,mid,L,R);
if (R>mid) ans+=query(rson[u],mid+1,r,L,R);
return ans;
}
int n;
void AddHs (int l,int r,ll x) {
//区间加上(a_i-x)^2
up(T[1],1,n,l,r,1);
up(T[2],1,n,l,r,-2ll*x);
up(T[3],1,n,l,r,1ll*x*x);
}
vector<int> g[maxn];
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],sz[maxn],top[maxn];
int lca (int x,int y) {
for (;top[x]!=top[y];dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]);
return dep[x]<dep[y]?x:y;
}
void upRange (int x,int y) {
int L=lca(x,y);
int A=dep[x];
int C=dep[L];
while (top[x]!=top[y]) {
if (dep[top[x]]<dep[top[y]]) {
AddHs(id[top[y]],id[y],(2ll*C-A-1));
y=fa[top[y]];
}
else {
AddHs(id[top[x]],id[x],A+1);
x=fa[top[x]];
}
}
if (dep[x]>=dep[y]) {
AddHs(id[y],id[x],A+1);
}
else {
AddHs(id[x],id[y],(2ll*C-A-1));
}
}
void dfs1 (int x,int f,int deep) {
dep[x]=deep;
fa[x]=f;
sz[x]=1;
int maxson=-1;
for (int y:g[x]) {
if (y==f) continue;
dfs1(y,x,deep+1);
sz[x]+=sz[y];
if (sz[y]>maxson) {
son[x]=y;
maxson=sz[y];
}
}
}
void dfs2 (int x,int topf) {
id[x]=++cnt;
top[x]=topf;
if (!son[x]) return;
dfs2(son[x],topf);
for (int y:g[x]) {
if (y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int main () {
scanf("%d",&n);
for (int i=1;i<n;i++) {
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i=1;i<=3;i++) T[i]=build(1,n);
int q;
scanf("%d",&q);
while (q--) {
int op;
scanf("%d",&op);
if (op==1) {
int x,y;
scanf("%d%d",&x,&y);
upRange(x,y);
}
else {
int x;
scanf("%d",&x);
ll ans=1ll*dep[x]*dep[x]*query(T[1],1,n,id[x],id[x])+1ll*dep[x]*query(T[2],1,n,id[x],id[x])+query(T[3],1,n,id[x],id[x]);
printf("%lld\n",ans);
}
}
}