[做题笔记] 树形分治/连通块问题练习
切树游戏
题目描述
点此看题
解法
话说树剖为什么会被卡啊？在洛谷上交了无数发最多 \(90\) 分，在 \(\tt loj\) 上倒是随便过，但是现在已经过了。
首先考虑不带修的暴力 \(dp\)，设 \(dp[u][i]\) 表示以 \(u\) 为最浅点的连通块，异或值为 \(i\) 的方案数。转移就是直接异或卷积，所以我们可以先把每个位置的点 \(\tt FWT\) 正变化，然后就可以直接点值相乘，最后求和再逆变化回去。
如果待修怎么办呢？考虑到我们要求出所有 \(dp[u]\) 的和再逆变换，所以我们再记一个 \(h[u][i]=\sum_{v\in subtree(u)} f[u][i]\)，那么最后维护出 \(h[1]\) 就可以了。这时候可以考虑用动态 \(dp\)，我们再处理出 \(lf[u][i]\) 表示只添加轻儿子时的 \(f[u][i]\)，\(lh[u][i]\) 表示只对轻儿子子树求和所得到的 \(h[u][i]\)
考虑第 \(i\) 位，现在要从节点 \(v\) 的 \((f[v][i],h[v][i],1)\) 变化到重链上父亲 \(u\) 的 \((f[u][i],h[u][i],1)\)，可以右乘上这样一个矩阵：
\[\begin{pmatrix} lf[u][i]&lf[u][i]&0\\ 0&1&0\\ lf[u][i]&lh[u][i]+lf[u][i]&1 \end{pmatrix} \]暴力乘可能很慢，考虑到这个矩阵比较稀疏，我们可以把它展开获得常数上的优化：
\[\begin{pmatrix}a_1&b_1&0\\0&1&0\\c_1&d_1&1\end{pmatrix} \times \begin{pmatrix}a_2&b_2&0\\0&1&0\\c_2&d_2&1\end{pmatrix} = \begin{pmatrix}a_1a_2&b_1+a_1b_2&0\\0&1&0\\a_2c_1+c_2&b_2c_1+d_1+d_2&1\end{pmatrix} \]并且我们发现只用维护四个位置上的值，这样就不用记录 \(3\times 3\) 的数组了。
此外因为本题的模数是 \(10007\)，但是在更新重链顶的父亲是，会出现将 \(lf[u][i]\) 做除法的情况，而如果除数是 \(0\) 自然就爆炸了，所以我们把这个数组写成 \(x\times 0^y\) 的形式，除以 \(0\) 的时候将 \(y\) 减 \(1\) 即可。
#include
#include
using namespace std;
const int M = 30005;
const int N = 130;
const int MOD = 10007;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,q,a[M],inv[M];vector g[M];
struct node
{
int x,y;
node() {x=y=0;}
void init(int a) {a?(x=a,y=0):(x=1,y=1);}
friend node operator * (node A,int b)
{
b%=MOD;
if(!b) A.y++;else A.x=A.x*b%MOD;
return A;
}
friend node operator / (node A,int b)
{
b%=MOD;
if(!b) A.y--;else A.x=A.x*inv[b]%MOD;
return A;
}
int val() {return y?0:x;}
};
void fwt(int *a,int n,int op)
{
for(int i=1;isiz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;num[u]=++Ind;
bot[u]=num[u];id[Ind]=u;
if(son[u])
dfs2(son[u],tp),bot[u]=bot[son[u]];
for(int v:g[u])
if(v^son[u] && v^fa[u])
dfs2(v,v);
}
void dfs3(int u)
{
for(int i=0;i>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
t[i]=t[i<<1|1]*t[i<<1];
}
void fuck(int i,int l,int r,int p)
{
if(l==r) {upd(i,id[l]);return ;}
int mid=(l+r)>>1;
if(mid>=p) fuck(i<<1,l,mid,p);
else fuck(i<<1|1,mid+1,r,p);
t[i]=t[i<<1|1]*t[i<<1];
}
tree ask(int i,int l,int r,int L,int R)
{
if(L<=l && r<=R) return t[i];
int mid=(l+r)>>1;
if(L>mid) return ask(i<<1|1,mid+1,r,L,R);
if(R<=mid) return ask(i<<1,l,mid,L,R);
return ask(i<<1|1,mid+1,r,L,R)
*ask(i<<1,l,mid,L,R);
}
void get(int x)
{
tree zz=ask(1,1,n,num[x],bot[x]);
for(int i=0;i 情报中心
题目描述
点此看题
解法
本题的关键是计算两条路径的并，那么计算并显然就要考察清楚两条路径的位置关系。但是路径的位置关系是不好考虑的，我们可以以点的位置关系代替路径的位置关系。设两条路径分别是 \((u_1,v_1),(u_2,v_2)\)，设 \(t=lca(u_1,u_2)\)，我们考虑在 \(t\) 这个点统计这两条路径的贡献，并且如果我们要求 \(t\) 是交路径上最深的点，情况数很大大减小：
（借用一下 cmd 的图）
设 \(c(x,y)=dis(x,y)-2\cdot v\)，那么不难发现，这两条路径的贡献是（注意最后要除以 \(2\)）：
\[ans=dis(u_1,u_2)+dis(v_1,v_2)+c(u_1,v_1)+c(u_2,v_2) \]因为我们是在 \(u_1,u_2\) 的 \(\tt lca\) 处统计的贡献，所以为了化简这个式子我们可以把 \(dis(u_1,u_2)\) 拆开：
\[w_{v_1}=c(u_1,v_1)+dist(u_1),w_{v_2}=c(u_2,v_2)+dist(u_2) \]\[ans=w_{v_1}+w_{v_2}+dis(v_1,v_2)-2\cdot dist(t) \]那么我们可以看成是 \(v_1,v_2\) 的带权匹配，由于可以把点权看成新建连在这个点下虚点的边权，所以这个带权匹配就是最大直径，那么就可以用直径合并的方法来维护了，合并两个点集只需要计算 \(6\) 次两两匹配。
那么我们考虑如何确保 \(t\) 是交路径上最深的点，对于路径 \((u,v)\) 设 \(lca=lca(u,v)\)，我们可以在 \([u,lca)\) 这些点的位置放置匹配点 \(v\)；在 \([v,lca)\) 这些位置放置匹配点 \(u\)，那么只有同一个位置上匹配点才能相互匹配。
现在这就是一个线段树合并的形式了，我们可以在 \(u/v\) 插入匹配点，然后在 \(lca\) 在 \(u/v\) 方向的第一个儿子处删除匹配点。以路径的编号建立线段树即可，上传定义为直径合并，时间复杂度 \(O(n\log n)\)
由于我卡常已经卡疯了，下面给出我没有卡过常的代码，只有 \(95\) 分，仅供理解。
#include
#include
#include
using namespace std;
const int M = 100005;
#define int long long
const int inf = 1e18;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,k,tot,f[M],fa[M][20];vector b[M];
int lg[M],dep[M],dis[M],dfn[M],dp[M][20];
int ans,cnt,rt[M],ls[M*40],rs[M*40];
struct node{int x,y;}tmp;
struct tree{node a,b;}o,zxy,t[M*40];
//zxy:use to make a clear
struct edge{int v,c,next;}e[M<<1];
//O(nlogn)-O(1) lca
void dfs(int u,int p)//initially dfs
{
dp[++m][0]=u;dfn[u]=m;
fa[u][0]=p;dep[u]=dep[p]+1;
for(int i=1;i<20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v,c=e[i].c;
if(v==p) continue;
dis[v]=dis[u]+c;dfs(v,u);
dp[++m][0]=u;
}
}
int Min(int x,int y)
{
return dep[x]>1]+1;
for(int j=1;(1<r) swap(l,r);
int k=lg[r-l+1];
return Min(dp[l][k],dp[r-(1<=0;i--)
if(dep[fa[x][i]]>dep[y])
x=fa[x][i];
return x;
}
int getd(int u,int v)
{
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
//segment-tree merge
int upd(int &mx,node u,node v)
{
if(!u.x || !v.x) return 0;
int c=u.y+v.y+getd(u.x,v.x);
if(c>mx) {mx=c;return 1;}
return 0;
}
int comb(tree &s,tree u,tree v)
{
int ret=0,mx=-inf;
//must consider the cases below
if(!u.a.x && !u.a.y) {s=v;return -inf;}
if(!v.a.x && !v.a.y) {s=u;return -inf;}
if(upd(mx,u.a,v.a)) s=tree{u.a,v.a};
if(upd(mx,u.a,v.b)) s=tree{u.a,v.b};
if(upd(mx,u.b,v.a)) s=tree{u.b,v.a};
if(upd(mx,u.b,v.b)) s=tree{u.b,v.b};
ret=mx;
if(upd(mx,u.a,u.b)) s=tree{u.a,u.b};
if(upd(mx,v.a,v.b)) s=tree{v.a,v.b};
return ret;
}
void up(int x)
{
if(!ls[x]) {t[x]=t[rs[x]];return ;}
if(!rs[x]) {t[x]=t[ls[x]];return ;}
comb(t[x],t[ls[x]],t[rs[x]]);
}
void ins(int &x,int l,int r,int id)
{
if(!x) x=++cnt;
if(l==r) {t[x].a=tmp;return ;}
int mid=(l+r)>>1;
if(mid>=id) ins(ls[x],l,mid,id);
else ins(rs[x],mid+1,r,id);
up(x);
}
void del(int &x,int l,int r,int id)
{
if(l==r) {t[x]=zxy;return ;}
int mid=(l+r)>>1;
if(mid>=id) del(ls[x],l,mid,id);
else del(rs[x],mid+1,r,id);
up(x);
}
int merge(int x,int y)
{
if(!x || !y) return x|y;
comb(t[x],t[x],t[y]);
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
return x;
}
void dfs2(int u)
{
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa[u][0]) continue;
dfs2(v);
ans=max(ans,comb(o,t[rt[u]],t[rt[v]])-2*dis[u]);
rt[u]=merge(rt[u],rt[v]);
}
for(int v:b[u]) del(rt[u],1,k,v);
}
void work()
{
n=read();ans=-inf;
for(int i=1;i