Q&A
Q：博主是哪里来的辣鸡，怎么才学点分治？
A：太弱了一直没完全搞懂，确实是弱鸡。
点分治
这个知识点很简单啊，关键怎么运用。
摆概念谁不会摆？
放找重心的代码
void getrt(int u,int pa=0)
{
siz[u]=1,w[u]=0;
for(int i=head[u],v;i;i=nxt[i])
if((v=to[i])!=pa&&!o[v])
getrt(v,u),siz[u]+=siz[v],w[u]=max(siz[v],w[u]);
w[u]=max(w[u],SZ-w[u]);
if(w[u]<w[rt])rt=u;
}
记得容斥，还有容斥的方法。
没了。
动态点分治
去年暑假的时候就学了点分治，一直懒得去搞动态的，但都快退役了还不学就凉了。
概念也很简单，solve的时候建出点分树，然后操作。
引用神仙(YCB)的课件
- 记得要减去来源子树的贡献。
- 常见的套路就是记下某个点 u 对其父亲的贡献 tofa[u] 。
- 这样查询跳点分树时就可以快速减去来源子树的贡献。
怎么操作？咕咕咕具体看题吧QAQ。
例题们：
ZJOI2015幻想乡战略游戏
sol
找带权重心，这个比较难，点分治并不是难点。
考虑式子的贡献可以一层一层累加，每次(p)的父亲(fa[p])对(u)的贡献为
[ans+=sum1_{fa[p]}-sum2_p+dis(fa[p],u)*(sum_{fa[p]}-sum_p)
]
其中(sum1)表示子树内的贡献和，(sum2)表示子树内到(fa)的贡献和，(sum)表示子树内的权值和。
至于(ans)的初值，那不就是(sum1_u)吗QAQ。
核心代码
void upd(int u,int e)
{
sum[u]+=e;
for(int p=u;fa[p];p=fa[p])
{
ll dis=get_dis(u,fa[p])*e;sum[fa[p]]+=e;
sum2[p]+=dis,sum1[fa[p]]+=dis;
}
}
ll calc(int u)
{
ll ans=sum1[u];
for(int p=u;fa[p];p=fa[p])
{
ans+=sum1[fa[p]]-sum2[p];
ans+=get_dis(fa[p],u)*(sum[fa[p]]-sum[p]);
}
return ans;
}
int find(int u)
{
int i,ans;
for(i=head[u];i&&sum[to[i]]<<1<sum[u];i=nxt[i]);
if(!i)return u;int p;ll del=sum[u]-sum[to[i]];
for(p=bj[i];p!=u;p=fa[p])sum[p]+=del;ans=find(to[i]);
for(p=bj[i];p!=u;p=fa[p])sum[p]-=del;return ans;
}
懒得放了。
动态点分治的(tofa)就是普通点分治的的容斥的动态形式，好像海星。