P6773 [NOI2020] 命运 题解

题意

给定一颗 $n$ 个节点的以 $1$ 有根树，每条边有权值 $a_i\in \{0,1\}$，给定 $m$ 个限制 $(u,v)$，保证 $u$ 是 $v$ 的祖先，要求 $u\rightarrow v$ 的路径上至少有 $1$ 条边的权值为 $1$，求满足条件的边权有多少种方案，对 $998244353$ 取模。

思路

设 $pre_x$ 表示对于所有限制 $(u_i,x)$，深度最大的 $u_i$，显然只有这一个限制有用，没有则为 $0$。

设 $f_{x,i}$ 表示以 $x$ 为根的子树中当前未满足的限制 $(u_i,v_i)$ 中深度最大的 $u_i$ 的深度为 $i$ 时的子树边权方案数。

考虑转移，从 $y$ 转移至 $x$，其中 $y$ 是 $x$ 的子节点。

当 $a_{(x,y)}=1$ 时，$y$ 及以下的限制都被满足了，$i$ 只于 $x$ 有关，所以转移为：

$$dp_{x,i}\leftarrow f_{x,i} \times \sum_{j=0}^{dep_y-1}f_{y,j}\ (0 \le i < dep_x)$$

当 $a_{(x,y)}=0$ 时，$y$ 及以下的限制可能没有被满足，此时的 $i$ 与 $x$ 和 $y$ 之间限制深度的较大值有关。

假如 $f_{x,i}$ 与 $x$ 有关，有 $f_{x,i} \leftarrow f_{x,i}\times \sum_{j=0}^{i}f_{y,j}$。

假如 $f_{x,i}$ 与 $y$ 有关，有 $f_{x,i} \leftarrow f_{y,i}\times \sum_{j=0}^{i}f_{x,j}$。

将以上转移结合起来，设 $g_{x,i}=\sum_{j=0}^{i}f_{x,i}$，转移即为：

$$f_{x,i}\leftarrow f_{x,i}\times(g_{y,dep_y-1}+g_{y,i})+f_{y,i}\times g_{x,i-1}\ (0 \le i < dep_x)$$

后面的 $g_{x,i-1}$ 是去掉了重复的 $f_{x,i}\times f_{y,i}$。

$O(n^2)$ 代码

void dfs2(int x,int xfa){
	f[x][pre[x]]=1;//初始化
	for(int j=0;j<dep[x];j++){
		g[x][j]=((j?g[x][j-1]:0)+f[x][j])%mod;//记录前缀和
	}
	for(int y:e[x])if(y!=xfa){
		dfs2(y,x);
		for(int j=0;j<dep[x];j++){
			f[x][j]=(f[x][j]*(g[y][dep[x]]+g[y][j])%mod+(j?f[y][j]*g[x][j-1]:0)%mod)%mod;//状态转移，注意f[x]的前缀和取得是上次的，不是这次的，所以前缀和要最后再统计
		}
		for(int j=0;j<dep[x];j++){
			g[x][j]=((j?g[x][j-1]:0)+f[x][j])%mod;
		}
	}
}

直接进行转移是 $n^2$ 的，考虑优化。

将数组改为vector，动态记录状态可以优化为 $O(n\times min(n,m))$。

注意到每个节点 $x$ 的 $f_{x,i}$ 中有用的状态并不多，考虑线段树合并。

对每个点建动态开点线段树，初始化 $f_{x,pre_x}=1$，其他为 0。$x$ 的线段树中节点 $p$ 表示的区间为 $[l,r]$，则节点 $p$ 维护的值为 $tr_{x,p}=\sum_{i=l}^{r}f_{x,i}$

目前主要问题是如何在进行线段树合并时维护转移。

首先由于需要计算前缀和，所以需要在合并过程中维护 $sx,sy$ 分别表示遍历到当前节点 $p$ 时 $[0,l-1]$ 的前缀和，即 $sx=\sum_{i=0}^{l-1}f_{x,i}\ ,\ sy=\sum_{i=0}^{l-1}f_{y,i}$。

在合并过程中主要处理的是当前只有 $x$ 的节点，只有 $y$ 的节点和叶子节点的转移。

当前只有 $x$ 的节点时，$sx$ 的更新很简单，就是加上当前值的和，即 $sx\leftarrow sx+tr_{x,p}$，对于 $tr_{x,p}$ 的更新，由于当前的 $sy=\sum_{i=0}^{l-1}$，并且在 $[l,r]$ 的区间内都为 $0$，所以可以直接用 $sy$ 更新 $tr_{x,p}$，即 $tr_{x,p}\leftarrow tr_{x,p}\times sy$。只有 $y$ 的节点同理。

对于叶子节点，将 $tr_{x,p}$ 和 $tr_{y,p}$ 都进行转移，再将权值合并至一起即可。需要注意的是转移前先更新 $sx$，转移后再更新 $sy$，这样可以去掉重复的 $f_{x,i}\times f_{y,i}$。

转移完后要将 $[dep_x,maxdep]$ 的部分置为 $0$，显然这部分都是不合法的，不能进行转移。

由于动态开点线段树总节点数是 $O(n \log n)$ 级的，所以时间复杂度 $O(n \log n)$。

代码

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,m;
vector<int> e[500010];
int pre[500010],dep[500010],mxdp;
void dfs1(int x,int xfa){
	dep[x]=dep[xfa]+1;
	mxdp=max(mxdp,dep[x]);
	for(int y:e[x])if(y!=xfa)dfs1(y,x);
}
struct N{
	int ls,rs;
	ll c,la;//值和乘法懒标记
}tr[20000010];//动态开点线段树节点数是O(n log n)的
int rt[500010],id;
void change(int &p,int l,int r,int x){//初始化f[x][pre[x]]=1
	if(!p){
		tr[p=++id]={0,0,1,1};//记得开新的节点懒标记和值要初始化为1
	}
	if(l==r)return ;
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x);
	else change(rc(p),mid+1,r,x);
}
void pushdown(int p){
	if(tr[p].la!=1){//乘法懒标记初始化是1
		if(lc(p)){
			tr[lc(p)].c=tr[lc(p)].c*tr[p].la%mod;
			tr[lc(p)].la=tr[lc(p)].la*tr[p].la%mod; 
		}
		if(rc(p)){
			tr[rc(p)].c=tr[rc(p)].c*tr[p].la%mod;
			tr[rc(p)].la=tr[rc(p)].la*tr[p].la%mod; 
		}
		tr[p].la=1;
	}
}
int merge(int x,int y,int l,int r,ll &sx,ll &sy){//线段树合并
	if(!x&&!y)return 0;
	if(!x){//只有y节点的情况
		sy=(sy+tr[y].c)%mod; 
		tr[y].c=tr[y].c*sx%mod;
        tr[y].la=tr[y].la*sx%mod;
		return y;
	}
	if(!y){//只有x节点的情况
		sx=(sx+tr[x].c)%mod;
		tr[x].c=tr[x].c*sy%mod;
        tr[x].la=tr[x].la*sy%mod;
		return x;
	}
	if(l==r){//叶子节点的情况
		sx=(sx+tr[x].c)%mod;//先更新sx后更新sy进行去重
		tr[x].c=(tr[x].c*sy%mod+tr[y].c*sx%mod)%mod;
		sy=(sy+tr[y].c)%mod;
		return x; 
	}
	int mid=(l+r)>>1;
	pushdown(x);pushdown(y);//记得pushdown
	lc(x)=merge(lc(x),lc(y),l,mid,sx,sy);//先往左边递归记录前缀和
	rc(x)=merge(rc(x),rc(y),mid+1,r,sx,sy);
	tr[x].c=(tr[lc(x)].c+tr[rc(x)].c)%mod;//记录答案
	return x;
}
void change0(int p,int l,int r,int x,int y){//区间赋值为0
	if(x>y)return ;
	if(!p)return ;
	if(l>=x&&r<=y){
		tr[p].la=tr[p].c=0;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(p);
	if(x<=mid)change0(lc(p),l,mid,x,y);
	if(y>mid)change0(rc(p),mid+1,r,x,y);
	tr[p].c=(tr[lc(p)].c+tr[rc(p)].c)%mod;
}
void dfs3(int x,int xfa){//树形dp
	change(rt[x],0,mxdp,pre[x]);//初始化
	for(int y:e[x])if(y!=xfa){
		dfs3(y,x);
		ll sx=0,sy=tr[rt[y]].c;
		rt[x]=merge(rt[x],rt[y],0,mxdp,sx,sy);//线段树合并
	}
	change0(rt[x],0,mxdp,dep[x],mxdp);//将不需要的部分复制为0
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0);
	cin>>m;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		pre[y]=max(pre[y],dep[x]);
	}
	dfs3(1,0);
	cout<<tr[rt[1]].c<<'\n';
	return 0;
}

这一切 , 都是 $\lfloor$ 命运 $\rceil$ 石之门的选择 !

(中二一下 , 咳咳咳

本文摘要

• 简要介绍了 $32pts$ (容斥) 的做法 , 详细介绍了 $64(72)pts$ (dp 方程的推导 , 深度的离散化 (虚树)) 和 $100pts$ (整体dp , 线段树合并) 的解法 .
• 由于我看各路大佬题解的线段树合并看了老半天没看懂 , 所以这一篇的线段树合并会讲的比较详细 , 可能更加适合像我一样没那么熟练链线段树合并的同学 .
• 同时 , 对于 dp 方程的推出有自然的想法 , 并非跳跃式的直接给出状态设计 . (不过对大佬来说确实一点都不跳跃
• 希望大家看得愉快 .

题意简述

题目中已经给出了形式化的描述 , 这里不再复述 . 为了下文叙述方便 , 我们把将一条边赋值为 $1$ 说成是染了色 , 把题目给出的带限制的链有时候简称为一个限制 .

$32pts$ : 容斥大法好 !

看到题目后 , 我一开始心态是崩的 : 我怎么只有 $n\times 2^n$ 的枚举算法 ? 完了呀 ... 但是你冷静一下 , 前面 $40pts$ 的 $m$ 都很小 - 也就是给定的树链 $(u,v)$ 很少 , 有什么用呢 ?

题目要求的是 : 所有给定的树链 , 其链上至少有 $1$ 条边被染色的方案数 . 我对着它冥思苦想 ... 没什么思路 , 不妨取问题的补集 , 也就是逆向思维 ? 可以等价于任意染色/不染色的方案数 $(2^{n-1})$ , 减去 : 至少存在一条给定树链 , 其链上没有边被染色的方案数 .

到了这里 , 就可以使用我们的容斥大法 . 枚举所有 $m$ 的子集 $S$ , 求出这个子集中所有被给定树链覆盖的边都不能染色的染色方案数 , 再乘以容斥系数 $(-1)^{|S|}$ 即可 . 该算法正确是因为 , 当 $|S|=0$ 时 , 我们加上了任意染色的方案数 $2^{n-1}$ : 此时所有合法的和不合法的方案都在里面 ; 当 $|S|=1$ 时 , 我们减去了 第 $1$ 条链 , 第 $2$ 条链 , $\dots$ , 第 $m$ 条链上没有任何一条边被染色的方案数 ; 但是这些链是会相交的 , 我们多减去了一些东西 , 所以我们还需要加上第 $i$ 条链和第 $j$ 条链均没有任何一条边被染色的方案数 ... 归纳地证明了容斥的正确性 . 写成式子 , 就是 :

$$\sum_{S\subset Q} (-1)^{|S|} 2^{n-1-|\cup_S|}$$

其中 $Q$ 是题目给定的树链的集合 , $|\cup_S|$ 表示 $S$ 集合内的树链求交之后 , 覆盖的边数 .

而我们发现 , 覆盖一条链的操作可以用树链剖分维护 , 所以总复杂度为 : $\mathcal O(m\times 2^m \log^2n)$ , 也可以优化到 $\mathcal O(2^m \log^2n)$ (不过没什么用 , 得分没有变化 ... 所以我 $40pts$ 的美梦破灭了

$64pts$ : dp 大法好 !

实际上容斥的做法 , 对于参加 NOI 的选手可能是小菜一碟的 . 那么更进一步的做法呢 ? 求方案数嘛 , 怎么想都和 dp 脱不了关系 . 而树上 dp 的设计肯定和子树有关 , 不妨先设计一个最 naive 的方程 :

$f_{x,0/1}$ 表示 , 所有树链限制 $(u,v)$ , 其两个端点都在 $x$ 子树内的限制都已经被满足 , 而 $v$ 在 $x$ 子树内 , $u$ 在 $x$ 子树外的限制没有/有 $(0/1)$ 被全部满足 , 的方案数 . 这是我们最初的想法 .

但是这是不可转移的 , 因为我们把所有链的信息浓缩在 $0/1$ 中 , 以至于我们从子节点 $y$ 向父节点 $x$ 转移时 , 我们无法确定边 $(x,y)$ 染色/不染色会造成的影响 . 主要影响是 , 当某个限制 $(u,v)$ 满足 $u=x$ , 且 $v$ 在 $y$ 的子树内时 , 从 $y$ 向 $x$ 的转移就出了问题 : 你不懂何时需要覆盖 $(x,y)$ 何时不需要 , 因为你不懂 $(u,v)$ 这个限制是否已经在 $y$ 的子树内得到满足 !

那我们尝试维护这个信息如何 ? 但是注意到 , $y$ 转移到 $x$ , $x$ 又会转移到 $x$ 的父亲 ... 这可能要求我们维护一个和深度有关的信息 . 一端 $u$ 在 $x$ 的子树外 , 一端 $v$ 在 $x$ 的子树内 , 那么显然所有 $u$ 都是 $x$ 的祖先 ... 等等 , 所有 $u$ 都是 $x$ 的祖先 ? 在看看题目的要求 : 所有给定链上至少有 $1$ 条边被染色 . 那么这就意味着 , 我们考虑所有尚未被满足的 $(u,v)$ , 且 $u$ 在 $x$ 子树外 , $v$ 在 $x$ 子树内 , 那么能使得它们合法的染色只可能是将 $(u,x)$ 中的某条边染色 ; 而最终情况下 , 必须让所有限制都合法 , 所以我们必须所有给 $u$ 中最深的 $(u_{\max},x)$ 中的某条边染色 ; 染色了 , 所有限制一并满足 ; 如果不是给 $(u_{\max},x)$ 上的某条边染色 , 那么 $(u_{\max},v)$ 这个限制将永远得不到满足 . 这就是其他题解中所说的 key observation .

所以 , 我们的 dp 方程新鲜出炉 : 设 $f_{x,i}$ 表示 $x$ 为根的子树中 , 两端点都在 $x$ 子树内的限制已经被满足 , 而对于尚未被满足的 $(u,v)$ , 且 $u$ 在 $x$ 子树外 , $v$ 在 $x$ 子树内 , 最深的 $u$ 的深度为 $i$ .

现在来考虑转移 . 首先 , 如果对于一个 $v$ , 题目给出了多个限制 $(u_1,v),(u_2,v)\dots$ , 那么最深的那个 $u$ 是有用的 . 设 $anc_v=u$ (ancestor , 祖先) , 当 $anc_v=0$ 时 , 说明没有限制 , 或者也可以认为是设置了虚点 $0$ , 该限制为 $(0,v)$ . 那么 , 对于 $f_{x,i}$ , 我们有 $\mathrm{dep}_{anc_x} \leq i < \mathrm{dep}_x$ , 因为对于限制 $(anc_x,x)$ , 无论你怎么给 $x$ 子树内的边染色 , 都不可能满足 ; 而 $i$ 也不能取到 $\mathrm{dep}_x$ (显然) .

好 . 接下来推导 $y\rightarrow x$ 的转移 . 当处理到子节点 $y$ 的时候 , $f_{x,i}$ 的值如何变化 :

$1.$ 对 $(x,y)$ 染色

那么所有端点 $v$ 在 $y$ 内的限制全部得到满足 . 所以贡献为

$$f_{x,i}\times \sum_{\mathrm{dep}_{anc_y} \leq j < \mathrm{dep}_y} f_{y,j}$$

噢 , 为了方便 , 不妨设 $g_{x,i}$ 为 $f_{x,i}$ 的前缀和 : $g_{x,i}=\sum_{j=0}^i f_{x,i}$ , 由于 $< \mathrm{dep}_{anc_x}$ 的部分都为 $0$ , 所以这个定义是合法的 .

所以贡献为 :

$$f_{x,i}\times g_{y,\mathrm{dep_y}-1}$$

$2.$ 对 $(x,y)$ 不染色

那么 , 如果 $y$ 中最深的限制是 $\leq i$ 的 , 那么合并后的子树的最深的限制仍然是 $i$ . 所以 , 贡献为 :

$$f_{x,i}\times g_{y,i}$$

但如果是 $>i$ 的 , 那么最深的限制可以有更浅的限制转移而来 , 贡献为 :

$$g_{x,i-1}\times f_{y,i}$$

整合起来就是 :

$$f_{x,i}\leftarrow f_{x,i}\times g_{y,\mathrm{dep_y}-1}+f_{x,i}\times g_{y,i}+g_{x,i-1}\times f_{y,i},\mathrm{dep}_{anc_x} \leq i < \mathrm{dep}_x$$

这样就有了 $\mathcal O(n^2)$ 的做法 . 但是注意到 , 有用的点 , 也就是作为限制的点 $u$ 是 $\mathcal O(\min(n,m))$ 级别的 . 所以 , 第二维 : 深度是可以离散化的 . 离散化后的第二维是 $\mathcal O(\min(n,m))$ 级别的 , 所有时空复杂度均为 $\mathrm O(n\min(n,m))$ , 可以拿到 $64pts$ 的好成绩 . 我对于这部分分有实现 , 下面是离散化这部分的代码 :

int main() {
	n=read();
	for(int i=1,x,y;i<n;++i) 
		x=read(),y=read(),add(x,y),add(y,x);
	dfs(1,0);
	m=read();dep[0]=0;
	for(int i=1;i<=m;++i) {
		int u=read(),v=read();
		anc[v]=dep[u] > dep[anc[v]] ? u : anc[v];
	}
	for(int i=1;i<=n;++i)
		if(anc[i])	rk[++cnt]=dep[anc[i]];
	sort(rk+1,rk+1+cnt),cnt=unique(rk+1,rk+1+cnt)-rk-1;
	rk[++cnt]=n;
	for(int i=1;i<=n;++i)
		dep[i]=lower_bound(rk+1,rk+1+cnt,dep[i])-rk;
	treedp(1,0);
	Writes(f[1][0]);
	return 0;
}

Q : 那么 $f,g$ 数组怎么开 ?

A : 当然是用 vector 啦 !

Q : 你为什么不用虚树 ? 你这样写 , $15,16$ 两个点会爆空间啊 ! $nm=10^9$ ...

A : 我忘记虚树了 ... 用虚树的话 , 时空复杂度变为 $\mathcal O(\min(n,m)^2)$ , 足以解决 $72pts$ 的问题 .

$100pts$ : 整体 dp - 线段树合并 !

好吧 , 这部分我无法自然地想出 qaq ... 我们对式子进行一些变化 :

$$f_{x,i}\leftarrow f_{x,i}\times (g_{y,\mathrm{dep_y}-1}+ g_{y,i})+f_{y,i}\times g_{x,i-1}$$

发现是对 $f_{x,i}$ 乘上某个数在加上 $f_{y,i}$ 乘上某个数 , 但是所谓的"这个数"是会变的啊 ?

不要紧 . 我们仍然考虑线段树合并 . 一开始 , 令 $f_{x,\mathrm{dep}_{anc_x}}=1$ . 维护两个全局值 $sum_x,sum_y$ , 来表示 $f_{x,i}/f_{y,i}$ 的前缀和 . 前缀和可以以引用的形式 (引用变量 , 或者设为全局变量也可以) , 在进入叶子结点或者 $x=0$ 或者 $y=0$ 时更新 . 而后在合并 $x$ 的子树和 $y$ 的子树时 : 我们发现难点在于当 $x=0$ 或者 $y=0$ 时 , 应该怎么维护下面的值呢 ?

当我们进入 $x=0$ 或者 $y=0$ 的结点时 , 看到我们的式子 , 就会发现 : $x=0,y\neq 0$ 时 , 说明在该结点内 $sum_x$ 将不会变化 , 且所有 $f_{x,i}$ 没有值 , 那么相当于整个子树全部同乘以一个数 : $g_{x,i-1}$ ; 而当 $x\neq 0,y=0$ 时 , 说明在该结点内 $sum_y$ 将不会变化 , 且所有 $f_{y,i}$ 没有值 , 那么相当于整个子树全部同乘以一个数 : $g_{y,\mathrm{dep_y}-1}+ g_{y,i}$ ; 而 $x\neq 0,y\neq 0$ 时 , 显然我们会继续往下合并 , 只需要 pushup 即可 .

而后需要注意 , 对于 $f_{x,i}$ , 由于只有 $\mathrm{dep}_{anc_x} \leq i < \mathrm{dep}_x$ 会有值 , 所以处理完子树转移后 , 我们需要将 $[0,\mathrm{dep_{anc_x}})$ 和 $[\mathrm{dep}_x,n]$ 区间赋值为 $0$ . (覆盖总是没问题的 , 不覆盖可能会出锅)

综上 , 我们维护区间和和乘法标记即可 (区间赋值为 $0$ 可以将乘法标记设为 $0$)

#define Lx (T[x].l)
#define Rx (T[x].r)
#define Ly (T[y].l)
#define Ry (T[y].r)
#define mid ((l+r)>>1)
int newp() {++cnt,T[cnt].mul=1;return cnt;}
void pushup(int x) {T[x].v=qmod(T[Lx].v+T[Rx].v);}
void pushdown(int x) {
	if(T[x].mul == 1)	return ;
	T[Lx].mul=1ll*T[Lx].mul*T[x].mul%mod,T[Lx].v=1ll*T[Lx].v*T[x].mul%mod;
	T[Rx].mul=1ll*T[Rx].mul*T[x].mul%mod,T[Rx].v=1ll*T[Rx].v*T[x].mul%mod;
	T[x].mul=1;
}
void insert(int x,int l,int r,int p) {
	if(l == r)	{T[x].v=1;return ;}
	if(p <= mid)	Lx=newp(),insert(Lx,l,mid,p);
	else	Rx=newp(),insert(Rx,mid+1,r,p);
	pushup(x);
}
int merge(int x,int y,int l,int r,int &sumx,int &sumy) {
	if(!x and !y)	return 0;
	if(!x) {
		sumy=qmod(sumy+T[y].v);
		T[y].mul=1ll*T[y].mul*sumx%mod,T[y].v=1ll*T[y].v*sumx%mod;
		return y;
	}
	if(!y) {
		sumx=qmod(sumx+T[x].v);
		T[x].mul=1ll*T[x].mul*sumy%mod,T[x].v=1ll*T[x].v*sumy%mod;
		return x;
	}
	if(l == r) {
		sumx=qmod(sumx+T[x].v);
		T[x].v=qmod(1ll*T[x].v*sumy%mod+1ll*T[y].v*sumx%mod);
		sumy=qmod(sumy+T[y].v);
		return x;
	}
	pushdown(x),pushdown(y);
	Lx=merge(Lx,Ly,l,mid,sumx,sumy);
	Rx=merge(Rx,Ry,mid+1,r,sumx,sumy);
	pushup(x);
	return x;
}
void cover(int x,int l,int r,int ql,int qr) {
	if(!x)	return ;
	if(ql <= l and r <= qr) {T[x].mul=0,T[x].v=0;return ;}
	pushdown(x);
	if(ql <= mid)	cover(Lx,l,mid,ql,qr);
	if(qr > mid)	cover(Rx,mid+1,r,ql,qr);
	pushup(x);
}
int query(int x,int l,int r,int p) {
	if(!x) return 0;
	if(l == r)	return T[x].v;	
	pushdown(x);
	return p<=mid?query(Lx,l,mid,p):query(Rx,mid+1,r,p);
}

void treedp(int x,int fa) {
	root[x]=newp();
	insert(root[x],0,maxdep,dep[anc[x]]);
	for(int i=head[x];i;i=nxt[i]) {
		int y=ver[i];
		if(y == fa)	continue;
		treedp(y,x);
		int sumx=0,sumy=T[root[y]].v;//g_{y,dep_y-1}
		root[x]=merge(root[x],root[y],0,maxdep,sumx,sumy);
	}
	cover(root[x],0,maxdep,dep[x],maxdep);
    
}

我从开始看这道题 , 然后写部分分 , 写正解 , 写题解 ... 一共断断续续地经过了 $10+$ 天 , 完结撒花 !