题解 P4842 【城市旅行】
万弘
2020-09-23 16:25:04
## 城市游行
tag:LCT,math.
介绍一种式子不同的方法。
先考虑这个 H 究竟是什么玩意。显然不能大力枚举路径去算，我们考虑每一个点的贡献：对于点 $ s $ ,记其与点 $ y $ 的距离为 $ \text{dep}(s) $ , $ x $ 到 $ y $ 的路径上点数为 $ all $ ,则贡献为 $ \text{dep}(s)*(all-\text{dep}(s)+1)*w(s) $
答案就是 $ \sum_{s\in path(x,y)}\text{dep}(s)*(all-\text{dep}(s)+1)*w(s) $
直接做是平方的，拆开来得到 $ ((all+1)\sum_s\text{dep}(s)*w(s))-\sum_s\text{dep}^2(s)*w(s) $
也就是说，我们要维护链上每个点深度乘点权的和，与深度的平方乘点权的和，同时要支持连边断边，链加。
记 $ s $ 的点权，点权和，深度和，深度平方和，深度乘点权和，深度平方乘点权和（以上均指以 $ s $ 为根的 splay 中的信息，“深度”均指到这个 splay 中最浅的点的距离+1）分别为 $ w(s), sumw(s),sumd(s),sumd2(s),dw(s),d2w(s) $ .
LCT 维护额外信息的关键在于 pushup，因此考虑如何通过左儿子 $ l $ ,右儿子 $ r $ 的信息来推出 $ x $ 的信息,记 $ x $ 的深度(左儿子大小+1）为 $ cur $ 。
点权和略。
$ sumd(s)=sumd(l)+cur+(sumd(r)+cur*size(r)) $
$ sumd2(s)=sumd2(l)+cur^2+(sumd2(r)+2cur*sumd(r)+size(r)*cur^2) $
$ dw(s)=dw(l)+cur*w(s)+(dw(r)+cur*sumw(r)) $
$ d2w(s)=d2w(l)+cur^2*w(s)+(d2w(r)+2cur*dw(r)+cur^2*sumw(r)) $
这几条的思路都是，左儿子不受影响， $ s $ 按定义算，然后算左儿子与 $ s $ 对右儿子的影响。
但是仅仅修改pushup是不够的。如果你像我那样仅仅改pushup，你会发现 $ w,sumw,sumd,sumd2 $ 都是对的，但 $ dw,d2w $ 是错的。
仔细观察~~debug~~ 可以发现， $ dw,d2w $ 的特殊之处在于，与splay的顺序有关（就是说，交换左右儿子，前面几个值不会改变，但 $ dw,d2w $ 会变化）。而LCT因为换根操作的存在，必然是有交换左右儿子的操作的，所以就挂掉了。要改对非常容易，我们再记录两个 $ Rdw,Rd2w $ 表示到splay中最深的点的距离+1的和，下传翻转标记的时候把当前点的 $ dw,Rdw $ 交换， $ d2w,Rd2w $ 交换就好了。
链加就不说了，和线段树上区间加是一个难度。
复杂度 $ \mathcal O(m\log n) $
写本文时间仓促，如有错漏恳请指出。
主要代码：
```cpp
#define MAXN 100011
struct LCT
{
int fa[MAXN],son[MAXN][2],rev[MAXN],w[MAXN],add[MAXN];
ll size[MAXN],sumw[MAXN],sumd[MAXN],sumd2[MAXN];
ll dw[MAXN],Rdw[MAXN],d2w[MAXN],Rd2w[MAXN];
void init(int n){for(int i=1;i<=n;++i)w[i]=read(),size[i]=1;}
bool not_root(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void pushrev(int x){if(x)std::swap(dw[x],Rdw[x]),std::swap(d2w[x],Rd2w[x]),std::swap(son[x][0],son[x][1]),rev[x]^=1;}//翻转
void pushadd(int x,int k)
{
if(!x)return;
sumw[x]+=size[x]*k,w[x]+=k,dw[x]+=sumd[x]*k,Rdw[x]+=sumd[x]*k, add[x]+=k;
d2w[x]+=sumd2[x]*k,Rd2w[x]+=sumd2[x]*k;
}
void pushup(int x)
{
int l=son[x][0],r=son[x][1];
ll cur=size[l]+1;
size[x]=size[l]+size[r]+1;
sumw[x]=sumw[l]+sumw[r]+w[x];
sumd[x]=sumd[l]+cur+(sumd[r]+cur*size[r]);
sumd2[x]=sumd2[l]+cur*cur+(sumd2[r]+2*cur*sumd[r]+size[r]*cur*cur);
dw[x]=dw[l]+cur*w[x]+(dw[r]+cur*sumw[r]);
d2w[x]=d2w[l]+cur*cur*w[x]+(d2w[r]+2*cur*dw[r]+cur*cur*sumw[r]);
cur=size[r]+1;
Rdw[x]=Rdw[r]+cur*w[x]+(Rdw[l]+cur*sumw[l]);
Rd2w[x]=Rd2w[r]+cur*cur*w[x]+(Rd2w[l]+2*cur*Rdw[l]+cur*cur*sumw[l]);
}
void pushdown(int x)
{
int l=son[x][0],r=son[x][1];
if(rev[x])pushrev(l),pushrev(r),rev[x]=0;
if(add[x])pushadd(l,add[x]),pushadd(r,add[x]),add[x]=0;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=(son[y][1]==x);
if(not_root(y))son[z][son[z][1]==y]=x;
fa[x]=z;
son[y][k]=son[x][!k],fa[son[x][!k]]=y;
son[x][!k]=y,fa[y]=x;
pushup(y),pushup(x);
}
int s[MAXN];
void splay(int x)
{
int top=0;
s[++top]=x;
for(int y=x;not_root(y);y=fa[y])s[++top]=fa[y];
while(top)pushdown(s[top--]);
while(not_root(x))
{
int y=fa[x];
if(not_root(y))rotate((son[y][1]==x)==(son[fa[y]][1]==y)?y:x);
rotate(x);
}
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),son[x][1]=y,pushup(x);
}
int get_root(int x)
{
access(x),splay(x);
while(son[x][0])x=son[x][0];
return splay(x),x;
}
void make_root(int x){access(x),splay(x),pushrev(x);}
bool split(int x,int y)
{
if(get_root(x)!=get_root(y))return 0;
make_root(x),access(y),splay(y);
return 1;
}
//
void Link(int x,int y)
{
if(get_root(x)!=get_root(y))make_root(x),fa[x]=y;//,printf("Link %d %d\n",x,y);
}
void Cut(int x,int y)
{
if(get_root(x)!=get_root(y))return;
split(x,y);
if(size[y]==2)fa[x]=0,son[y][0]=0,pushup(y);//,printf("Cut %d %d\n",x,y);
}
void Add(int x,int y,int k){if(split(x,y))pushadd(y,k);}
void solve(int x,int y)
{
if(split(x,y))
{
ll a=(size[y]+1)*dw[y]-d2w[y],b=size[y]*(size[y]+1)/2,g=gcd(a,b);
printf("%lld/%lld\n",a/g,b/g);
}
else puts("-1");
}
}lct;
```