Blog Detail

C20250053's blog
省集笔记（4.20~4.24）
C20250053 LV 9 @ 2026-6-7 12:01:36

4.20

A

考虑转而刻画一条路径合法的条件。

我们设一条路径上同色段的长度分别为 $L_1\sim L_t$ ，那么对于 $L_i>k$ ，需要翻转至少 $\lfloor\frac{L_i}{k+1}\rfloor$ 条边。

所以路径合法当且仅当 $\sum_{i=1}^t\lfloor\frac{L_i}{k+1}\rfloor\le m$ 。

我们对于一条从分治中心出发的半路径，同色段分别为 $L_1\sim L_t$ ，维护 $val_L=L_1+(k+1)\sum_{i=2}^t\lfloor\frac{L_i}{k+1}\rfloor$，

考虑当我们把同色的两条半路径 $A_1\sim A_{t_A},B_1\sim B_{t_B}$ 拼在一起，得到 $A_1+B_1+(k+1)\Big(\sum_{i=2}^{t_A}\lfloor\frac{A_i}{k+1}\rfloor+\sum_{i=1}^{t_B}\lfloor\frac{B_i}{k+1}\rfloor\Big)$，除以 $k+1$ 向下取整：

$$\lfloor\frac{val_A+val_B}{k+1}\rfloor=\\ \Big\lfloor\frac{A_1+B_1+(k+1)\Big(\sum_{i=2}^{t_A}\lfloor\frac{A_i}{k+1}\rfloor+\sum_{i=2}^{t_B}\lfloor\frac{B_i}{k+1}\rfloor\Big)}{k+1}\Big\rfloor\\ =\Big\lfloor\frac{A_1+B_1}{k+1}\Big\rfloor+\sum_{i=2}^{t_A}\lfloor\frac{A_i}{k+1}\rfloor+\sum_{i=1}^{t_B}\lfloor\frac{B_i}{k+1}\rfloor \le m$$

移项得到 $val_A+val_B<(m+1)(k+1)\Rightarrow val_A\le (m+1)(k+1)-1-val_B$。

然后异色的情况更加简单，有：

$$\lfloor\frac{val_A}{k+1}\rfloor+\lfloor\frac{val_B}{k+1}\rfloor\le m\\ \Rightarrow \lfloor\frac{val_A}{k+1}\rfloor\le m-\lfloor\frac{val_B}{k+1}\rfloor\\ \Rightarrow val_A<((m+1)-\lfloor\frac{val_B}{k+1}\rfloor)(k+1)\\ \Rightarrow val_A\le (m+1)(k+1)-1-\lfloor\frac{val_B}{k+1}\rfloor(k+1)$$

所以我们令 $S=(m+1)(k+1)-1$ ，然后因为 $val$ 均 $\le n$ ，所以 $S$ 可以和 $2n$ 取 $\min$ 。

点分治 + 树状数组维护即可。

时间复杂度 $\mathcal{O}(n\log^2n)$ ，点分治 $1\log$ ，树状数组 $1\log$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e5 + 10;

int n,m,K,S,rt=-1,ans=0;
int siz[MAXN],mx[MAXN];
vector<PII>G[MAXN];
bool vis[MAXN];

struct BIT{
	#define lowbit(x) (x&(-x))
	int c[MAXN];
	int st[MAXN],top=0;
	void update(int x,int k){
		st[++top]=x;
		while(x<=n){
			c[x]=max(c[x],k);
			x+=lowbit(x);
		}
	}
	int query(int x){
		int res=0;
		while(x){
			res=max(res,c[x]);
			x-=lowbit(x);
		}
		return res;
	}
	void clear(){
		while(top){
			int x=st[top];
			while(x<=n){
				c[x]=0;
				x+=lowbit(x);
			}
			top--;
		}
	}
}T[2];

void Get_rt(int u,int fth,int sum){
	siz[u]=1,mx[u]=0;
	for(auto i:G[u]){
		int v=i.first;
		if(v==fth||vis[v]) continue;
		Get_rt(v,u,sum);
		mx[u]=max(mx[u],siz[v]);
		siz[u]+=siz[v];
	}
	mx[u]=max(mx[u],sum-siz[u]);
	if(rt==-1||mx[rt]>mx[u]) rt=u;
}

vector<PII>V;

void dfs(int u,int fth,int val,int dep,int len,int col,bool op){
	siz[u]=1;
	V.push_back({val+(op?(dep/K)*K:dep),len});
	for(auto i:G[u]){
		int v=i.first,w=i.second;
		if(v==fth||vis[v]) continue;
		if(w==col) dfs(v,u,val,dep+1,len+1,w,op);
		else dfs(v,u,val+(op?(dep/K)*K:dep),1,len+1,w,1);
		siz[u]+=siz[v];
	}
}

void solve(int u){
	for(auto i:G[u]){
		int v=i.first,w=i.second;
		if(vis[v]) continue;
		V.clear(),dfs(v,u,0,1,1,w,0);
		for(auto j:V){
			int val=j.first,len=j.second;
			if(val>S) continue;
			ans=max(ans,len+max({0,T[w].query(min(n,S-val)),T[!w].query(min(n,S-(val/K)*K))}));
		}
		for(auto j:V){
			int val=j.first,len=j.second;
			if(val>S) continue;
			T[w].update(val,len);
		}
	}
	vis[u]=1;
	T[0].clear(),T[1].clear();
	for(auto i:G[u]){
		int v=i.first;
		if(vis[v]) continue;
		rt=-1,Get_rt(v,u,siz[v]);
		solve(rt);
	}
}

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int Id;
	scanf("%d%d%d%d",&Id,&n,&K,&m),K++;
	S=min(2ll*n,1ll*(m+1)*K-1);
	FL(i,1,n-1){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	rt=-1,Get_rt(1,0,n);
	solve(rt);
	printf("%d\n",ans);
}

B

原题 QOJ10072

对于排列 $P$ ，我们定义点 $x$ 的权值为 $r_x=pos_P(x)$ ，那么交互库会返回 $r_x$ 小于两个邻居的 $r$ 的 $x$ ，也就是环上的所有局部最小值点。

我们随机一个排列 $P$ 给所有点赋权，询问一次找出所有局部最小值点（谷底），然后翻转 $P$ 找出所有局部最大值点（峰），然后我们从谷底开始，一层层找出距离谷底为 $1,2,3,\cdots$ 的点，然后选出距离为 $0,2,4,\cdots$ 的点，然后加上峰，得到类似独立集的 $S'$ ，然后把不是独立集的剔除（ $val_i=1$ 的 $i\in S$ ，因为距离为偶数的点之间不会互相影响，所以如果有 $i'\in S'$ ， $val_{i'}=0$ ，那么说明它和某个距离为偶数的点相邻了），得到独立集 $S$ 。

此时令 $T=[n]/S$ ，那么 $S$ 中的点的两个邻居都在 $T$ 中。

考虑如何确定 $i(i\in S)$ 的邻居，考虑把 $i$ 插在 $T$ 的第 $j$ 个点和第 $j+1$ 个点中间，如果此时 $i$ 是最小值点，那么 $i$ 靠后的邻居在 $T$ 中的位置也 $\le j$ ，于是找到最大的满足的 $j$ ， $T_j$ 就是 $i$ 的邻居，我们把这个算法拓展到 $i$ 中所有点也就是做整体二分，然后把 $T$ 翻转再做一次，得到 $S$ 中所有点的两个邻居，

此时 $T$ 中还有一些点邻居数量 $<2$ ，我们考虑将这些点扔到序列最前面进行询问，那么对于一条未被还原的边 $(u,v)$ ， $u,v$ 一定有其中一个成为局部最小值点被返回，按照返回值将这些点分为两个集合，发现所有边的端点都在不同集合，做和匹配 $S-T$ 一样的算法即可。

时间复杂度 $\mathcal{O}(n\log^2n)$ 。

#include"findseat.h"
#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n;
vector<int>ans;
bitset<MAXN>vis,val,us;
vector<int>G[MAXN];
bool vmn[MAXN],vmx[MAXN];

void Qry(vector<int> P){
	vis.reset(),val.reset();
	for(int i:P) vis.set(i);
	FL(i,1,n)
		if(!vis[i]) P.push_back(i);
	vector<int>res=query(P);
	for(int i:res) val.set(i);
}

int L[MAXN],R[MAXN];

void Solve(vector<int> S,vector<int> T){
	for(int i:T) L[i]=0,R[i]=(int)S.size();
	while(1){
		vector<int>Q;
		vector<PII>tmp;
		for(int i:T) if(L[i]<R[i]) tmp.push_back({(L[i]+R[i])/2,i});
		if(tmp.empty()) break;
		sort(tmp.begin(),tmp.end());
		int j=0;
		for(int i=0;i<(int)S.size();i++){
			Q.push_back(S[i]);
			while(j<(int)tmp.size()&&tmp[j].first==i)
				Q.push_back(tmp[j].second),j++;
		}
		Qry(Q);
		for(auto i:tmp){
			int mid=i.first,id=i.second;
			if(val[id]) L[id]=mid+1;
			else R[id]=mid;
		}
	}
	for(int i:T)
		if(L[i]<(int)S.size())
			G[S[L[i]]].push_back(i),G[i].push_back(S[L[i]]);
}

void dfs(int u){
	ans.push_back(u),us[u]=1;
	for(int v:G[u])
		if(!us[v]) dfs(v);
}

vector<int> solve(int N,int Id){
	n=N;
	if(n==1) return {1};
	vector<int>P(n);
	FL(i,0,n-1) P[i]=i+1;
	shuffle(P.begin(),P.end(),rnd);
	Qry(P);
	vector<int>st;
	for(int i:P) if(val[i]) st.push_back(i),us[i]=vmn[i]=1;
	reverse(P.begin(),P.end());
	Qry(P);
	for(int i:P) if(val[i]) us[i]=vmx[i]=1;
	reverse(P.begin(),P.end());
	int dep=1;
	while((int)us.count()<n){
		vector<int>Q;
		for(int i:P) if(!us[i]) Q.push_back(i);
		Qry(Q),us|=val;
		if(!(dep&1))
			for(int i:Q)
				if(val[i]) st.push_back(i);
		dep++;
	}
	for(int i:P) if(vmx[i]) st.push_back(i);
	Qry(st),us.reset();
	vector<int>S,T;
	for(int i:st) if(val[i]) S.push_back(i),us[i]=1;
	FL(i,1,n) if(!us[i]) T.push_back(i);
	Solve(T,S);
	reverse(T.begin(),T.end());
	Solve(T,S);
	P.clear();
	FL(i,1,n)
		if(G[i].size()<2) P.push_back(i);
	Qry(P),S.clear(),T.clear();
	for(int i:P){
		if(!val[i]) S.push_back(i);
		else T.push_back(i);
	}
	Solve(S,T);
	us.reset(),dfs(1);
	return ans;
}

4.21

A

显然对于每个 $i$ ，如果你把 $i\to p_i$ 的边拉出来，会形成基环树森林。

然后问题等价于初始每个节点上有一个棋子，在 $K$ 轮中，每个棋子每轮都有 $\frac12$ 的概率沿出边移动，且每个棋子的移动概率相对独立。

最后问 $K$ 轮之后有至少一个棋子停留的节点的期望个数。

发现至少一个是难算的，正难则反，考虑算最后没有棋子停留的节点的期望个数。

根据期望的线性性质，设 $p_i$ 为最后节点 $i$ 没有棋子停留的概率，那么期望个数就是 $\sum p_i$ 。

考虑如何计算 $p$ ，令 $q_{i,j}$ 表示棋子 $i$ 最终移动到节点 $j$ 的概率，有 $p_j=1-\prod_i(1-q_{i,j})$ 。

答案为 $\displaystyle\sum_{j=1}^n\Big(1-\prod_i(1-q_{i,j})\Big)$。

我们设 $P_i$ 表示 $K$ 轮走 $i$ 步的概率，有 $P_i=\frac{1}{2^K}\binom{K}{i}$ 。

考虑如何计算 $q_{i,j}$ ，因为每个点出度为 $1$ ，所以是内向基环树，每个点出发经过的路径一定是链 + 环，设 $i,j$ 的距离为 $d$ ，分类讨论：

若 $j$ 在链上，那么 $i$ 最后到 $j$ 当且仅当恰好走了 $d$ 步， $q_{i,j}=P_d$ 。
若 $j$ 在环上，设环长为 $L$ ，那么 $i$ 最后到 $j$ 可能走了 $d+kL(k\ge0)$ 步，因此 $q_{i,j}=\displaystyle\sum_{t\ge d\land t\equiv d\pmod L}P_t$。

发现 $q_{i,j}$ 只和 $d$ 和 $L$ 有关，因为环长的总和是 $\mathcal{O}(n)$ ，所以互不相同的环长只有 $\mathcal{O}(\sqrt{n})$ 种于是可以预处理每个 $d,L$ 的答案，时间复杂度 $\mathcal{O}(K\sqrt{n})$ 。

最后枚举 $i$ ，然后暴力走出边遍历 $j$ ，计算出 $q_{i,j}$ 然后乘到 $p_j$ 里去，时间复杂度 $\mathcal{O}(n^2)$ 。

总时间复杂度 $\mathcal{O}(K\sqrt{n}+n^2)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e3 + 10;
const int MAXK = 3e5 + 10;
const int MAXB = 80 + 5; 
const int mod = 998244353;
const int inv2 = (mod+1)/2;

int n,K,Ans;
int nxt[MAXN],deg[MAXN],ans[MAXN];
int len[MAXN],id[MAXN],idx=0;
int sum[MAXB][MAXK];
int fac[MAXK],inv[MAXK],P[MAXK];
bool vis[MAXN];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int C(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; 
}

int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout); 
	scanf("%d%d",&n,&K),Ans=n;
	fac[0]=1;
	FL(i,1,K) fac[i]=1ll*fac[i-1]*i%mod;
	inv[K]=qpow(fac[K],mod-2);
	FR(i,K-1,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	int Mul=qpow(inv2,K);
	FL(i,0,K) P[i]=1ll*Mul*C(K,i)%mod;
	FL(i,1,n) scanf("%d",&nxt[i]),deg[nxt[i]]++;
	queue<int>q;
	FL(i,1,n)
		if(!deg[i]) q.push(i);
	while(!q.empty()){
		int u=q.front(),v=nxt[u];
		q.pop();
		deg[v]--;
		if(!deg[v]) q.push(v);
	}
	FL(i,1,n){
		if(!deg[i]||vis[i]) continue;
		int j=nxt[i],dis=0;
		vis[i]=1,dis++;
		while(j!=i) vis[j]=1,dis++,j=nxt[j];
		len[i]=dis,j=nxt[j];
		while(j!=i) len[j]=dis,j=nxt[j];
		if(id[dis]) continue;
		id[dis]=++idx;
		FR(j,K,0){
			sum[idx][j]=P[j];
			if(j+dis<=K) sum[idx][j]=(sum[idx][j]+sum[idx][j+dis])%mod;
		}
	}
	FL(i,1,n) ans[i]=1;
	FL(i,1,n){
		int j=i,dis=0;
		while(!len[j]){
			ans[j]=1ll*ans[j]*(1-P[dis]+mod)%mod;
			j=nxt[j],dis++;
		}
		int St=j,Id=id[len[St]];
		ans[j]=1ll*ans[j]*(1-sum[Id][dis]+mod)%mod;
		j=nxt[j],dis++;
		while(j!=St) ans[j]=1ll*ans[j]*(1-sum[Id][dis]+mod)%mod,dis++,j=nxt[j];
	}
	FL(i,1,n) Ans=(Ans-ans[i]+mod)%mod;
	printf("%d\n",Ans);
}

B

发现对于一个点 $x$ ，设其祖先方向编号最小/最大的点分别为 $y,z$ ，因为 $y,z$ 均为 $x$ 的祖先所以 $y,z$ 之间也有祖先关系，不妨设 $dep_y>dep_z$ ，则存在边 $x\to y,x\to z,y\to z$ ， $x\to z$ 对连通性无影响，可以删去，即对于每个 $x$ 只保留一条向上的边 $x\to nxt_x$ 。

发现可以到达点 $x$ 的祖先是一段后缀，如果某个祖先 $y$ 可以到达 $x$ ，那么 $y$ 到 $x$ 路径上的所有点也都可以到达 $x$ ，我们设这个分界点为 $lim_x$ ， $dep_y\ge lim_x$ 的祖先 $y$ 可以到达 $x$ 。

（设 $z$ 是 $y$ 到 $x$ 路径上的儿子，因为 $x$ 在 $z$ 的子树中，那么 $y$ 一定通过 $z$ 的一个祖先 $t$ 向下进入了 $z$ 的子树，是 $t\to mn_t/t\to mx_t$ ，此时 $mn_t/mx_t$ 是 $t$ 子树内编号最小/最大的节点，然后我们发现如果 $mn_t/mx_t\not=z$ ， $z$ 的子树被 $t$ 的子树包含，所以 $mn_t\le mn_z,mx_t\ge mx_z$ ，否则跳到 $z$ ，显然这种情况 $z$ 能跳到 $t$ 。

综上，如果 $y$ 能到达 $x$ ， $z$ 也能到达 $x$ ）。

$lim$ 是容易计算的，我们按照深度从小到大枚举点 $x$ ，然后把所有未曾被到达且被 $x$ 到达的点的 $lim$ 标记为 $dep_x$ ，因为是从小到大枚举，所以得到的 $lim$ 一定是最小的 $lim$ ，因为每个点最多只会被拓展一次所以是 $\mathcal{O}(n)$ 的。

然后我们希望计算答案，我们枚举终点 $v$ ，

一个点 $u$ 能到达 $v$ 当且仅当它向上跳时，可以进入根到 $v$ 链上深度至少为 $lim_v$ 的区域，

为了不重复计算，我们取 $u$ 的向上链上，深度最小但仍然满足 $dep_x\ge lim_v$ 的 $v$ 的祖先点 $x$ ，那么 $x$ 要满足 $x$ 是 $v$ 的祖先且 $dep_{nxt_x}<lim_v\le dep_x$ ，

我们令 $sum_x$ 表示所有只通过向上跳能到达 $x$ 的点的点权和。

（发现如果有点 $y$ 向下走到 $z$ 可以再向上到达 $x$ ，此时从 $y$ 直接向上跳一定能到达 $x$ ，因为 $y$ 的祖先链被 $z$ 的祖先链包含，显然限制更少）。

我们递归遍历 $v$ ，我们用树状数组维护 $dep_{nxt_x}<lim_v$ 的 $sum_x$ 的和 $Sum$ ，然后注意 $dep_x<lim_v$ 的也被计算了，所以我们在遍历过程中 $prv_d$ 表示 $rt$ 到 $v$ 的路径上深度 $\le d$ 的 $x$ 的 $sum_x$ 之和，再减去 $v$ 自己的权值 $w_v$ ，对答案的贡献就是 $(Sum-prv_{lim_u-1}-w_v)\times w_v$ 。

时间复杂度 $\mathcal{O}(n\log n)$ ，线性的我不会。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e6 + 10;
const int mod = 1e9 + 7;

int n,rt;
ll ans=0;
int dep[MAXN],fa[MAXN],w[MAXN];
vector<int>G[MAXN],V[MAXN]; 
int mx[MAXN],mn[MAXN],nxt[MAXN],lim[MAXN];
ll sum[MAXN],prv[MAXN];

struct BIT{
	#define lowbit(x) (x&(-x))
	ll c[MAXN];
	void update(int x,int k){
		x++;
		while(x<=n+1){
			c[x]=(c[x]+k+mod)%mod;
			x+=lowbit(x);
		}
	}
	ll query(int x){
		ll res=0;
		x++;
		while(x){
			res=(res+c[x])%mod;
			x-=lowbit(x);
		}
		return res;
	}
}T;

void dfs1(int u,int pmx,int pmn){
	dep[u]=dep[fa[u]]+1;
	V[dep[u]].push_back(u);
	if(fa[u]) nxt[u]=(dep[pmx]>dep[pmn]?pmx:pmn);
	mx[u]=0,mn[u]=n+1,sum[u]=w[u];
	for(int v:G[u]){
		dfs1(v,max(pmx,u),min(pmn,u));
		mx[u]=max({mx[u],mx[v],v});
		mn[u]=min({mn[u],mn[v],v});
	}
	sum[nxt[u]]=(sum[nxt[u]]+sum[u])%mod;
}
void dfs2(int u){
	if(nxt[u]&&lim[nxt[u]]==n) lim[nxt[u]]=lim[u],dfs2(nxt[u]);
	if(1<=mn[u]&&mn[u]<=n&&lim[mn[u]]==n) lim[mn[u]]=lim[u],dfs2(mn[u]);
	if(1<=mx[u]&&mx[u]<=n&&lim[mx[u]]==n) lim[mx[u]]=lim[u],dfs2(mx[u]);
}
void dfs3(int u){
	prv[dep[u]]=prv[dep[u]-1]+sum[u];
	T.update(dep[nxt[u]],sum[u]);
	ans=(ans+1ll*((T.query(lim[u]-1)-prv[lim[u]-1]-w[u])%mod+mod)%mod*w[u]%mod)%mod;
	for(int v:G[u]) dfs3(v);
	T.update(dep[nxt[u]],-sum[u]);
}

int main(){
	freopen("starmap.in","r",stdin);
	freopen("starmap.out","w",stdout); 
	int ID,Num;
	scanf("%d%d",&ID,&Num);
	while(Num--){
		scanf("%d",&n),rt=-1,ans=0;
		FL(i,1,n) G[i].clear(),V[i].clear(),lim[i]=n,nxt[i]=0;
		FL(i,1,n){
			scanf("%d",&fa[i]);
			if(!fa[i]) rt=i;
			G[fa[i]].push_back(i);
		}
		FL(i,1,n) scanf("%d",&w[i]);
		dfs1(rt,0,n+1);
		FL(i,1,n)
			for(int u:V[i]) 
				if(lim[u]==n) lim[u]=i,dfs2(u);
		dfs3(rt);
		printf("%lld\n",ans);
	} 
}

C

考虑环上的点 $u$ 所在子树的深度极差，也就是 $u$ 向非环的方向走，可以走的最长长度。

于是我们发现，我们只需要对于每个点维护这个点出发的前三长的可用路径，当这个点在环上时，子树深度 $h$ 一定是其中之一。

对于某条路径，假设路径上所有环点的子树深度集合为 $H=\{h_1,h_2,\cdots,h_m\}$ 。

题目要求 $\max\{H\}-\min\{H\}\le K$ ，等价于存在整数 $x$ ，使得 $\forall h_i,h_i\in [x,x+K]$ 。

那么我们也可以反过来钦定合法的 $x$ 的范围， $x\in \bigcap_{h\in H}[h-K,h]$ ，如果交集非空说明这条路径的深度极差不超过 $K$ 。

因为我们要统计所有点对，所以考虑点分治。

统计从当前重心 $u$ 出发的半路径，并不断和到达点的 $[h_v-K,h_v]$ 取交集，当到达点 $v$ 的时候假设 $x$ 的可用区间为 $[L,R]$ ，那么 $v$ 作为 $x\in[L,R]$ 可用的点加入扫描线，然后继续往 $v$ 的子树里走，找到不是 $fa_u$ 也不是 $v$ 的 $u$ 出发的最大深度 $h_u$ ，把 $[L,R]$ 和 $[h_u-K,h_u]$ 取交。

然后扫描线记录三个东西， $sum_{v}$ 表示以 $u$ 为根时， $v\in son(u)$ 的 $v$ 子树中有多少个可用的点，$sum_1=\sum_{v\in son(u)}sum_{v},sum_2=\sum_{v\in son(u)}\binom{sum_v}{2}$。

考虑重心 $u$ 自己贡献的深度，设贡献最大/次大深度的子树根分别为 $p,q,r$ ：

如果贡献最大深度，那么 $p$ 一定不被占用，有 $S=sum_1-sum_p$ 个点不在 $p$ 中，点对数是 $S+\binom{S}{2}-(sum_2-\binom{sum_p}{2})$ （ $S$ 是一个端点是 $u$ ， $\binom{S}{2}$ 是随便选，减去在一个子树内选两个的非法情况）。
如果贡献次大深度，那么 $p$ 一定被占用， $q$ 一定不被占用，点对数是 $sum_p+sum_p\cdot(sum_1-sum_p-sum_q)$ 。
否则 $p,q$ 一定都被占用，点对数是 $sum_p\cdot sum_q$ 。

注意有系数，如果当前事件位置是 $x$ ，下一个事件位置是 $x'$ ，那么对于区间 $[x,x')$ ，可用端点集合相同，所以乘 $x'-x$ 。

（为了保证一段内可用端点集合以及计算答案的区间相同，我们要对于 $u$ 的三个深度 $h_p,h_q,h_r$ ，加入 $[h_p-K,h_p],[h_q-K,h_p],[h_r-K,h_r]$ ）

然后因为一条合法路径会被多个 $x$ 重复计算，所以我们算一遍 $K$ 的答案，减去 $K-1$ 的答案，此时条合法路径恰好被算一次。

考虑一条 $mx=\max\{H\},mn=\min\{H\}$ ，极差 $d=mx-mn$ 的路径，

会算到它的 $x$ 要满足 $x\le mn,mx\le x+K$ ，所以 $x\in [mx-K,mn]$ ，

会被计算 $\max(0,mn-(mx-K)+1)=\max(0,K-d+1)$ 次，

当 $K\to K-1$ 时，会被计算 $\max(0,mn-(mx-(K-1))+1)=\max(0,(K-1)-d+1)$ ，

当 $K\ge d$ 时作差为 $1$ ，否则为 $0$ ，正好是路径合法时的定义，每条合法路径只会算一次。

时间复杂度 $\mathcal{O}(n\log^2 n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;

const int MAXN = 1e5 + 10;

int n,K,rt;
ll ans=0;
int Dw[MAXN],Up[MAXN];
int siz[MAXN],mx[MAXN];
vector<int>G[MAXN];
vector<PII>E[MAXN];
bool vis[MAXN];

void dfs1(int u,int fth){
	for(int v:G[u]){
		if(v==fth) continue;
		dfs1(v,u);
		E[u].push_back({Dw[v]+1,v});
	}
	sort(E[u].begin(),E[u].end(),greater<PII>());
	E[u].resize(3,{0,0});
	Dw[u]=E[u][0].first; 
}
void dfs2(int u,int fth){
	for(int v:G[u]){
		if(v==fth) continue;
		Up[v]=max(Up[u]+1,E[u][(v==E[u][0].second?1:0)].first+1);
		dfs2(v,u);
	}
	if(fth) E[u].push_back({Up[u],fth});
	sort(E[u].begin(),E[u].end(),greater<PII>());
	E[u].resize(3,{0,0});
}
void Get_siz(int u,int fth){
	siz[u]=1;
	for(int v:G[u]){
		if(v==fth||vis[v]) continue;
		Get_siz(v,u);
		siz[u]+=siz[v];
	}
}
void Get_rt(int u,int fth,int sum){
	siz[u]=1,mx[u]=0;
	for(int v:G[u]){
		if(v==fth||vis[v]) continue;
		Get_rt(v,u,sum);
		mx[u]=max(mx[u],siz[v]);
		siz[u]+=siz[v];
	}
	mx[u]=max(mx[u],sum-siz[u]);
	if(rt==-1||mx[rt]>mx[u]) rt=u;
}
int Qry(int u,int x,int y){
	for(auto i:E[u])
		if(i.second!=x&&i.second!=y) return i.first;
	return -1;
}

vector<PII>Q;

void dfs4(int u,int fth,int K,int L,int R,int tp){
	int mxd=Qry(u,fth,-1),l=max(L,mxd-K),r=min(R,mxd);
	if(l<=r) Q.push_back({l,tp}),Q.push_back({r+1,-tp});
	for(int v:G[u]){
		if(v==fth||vis[v]) continue;
		mxd=Qry(u,fth,v);
		dfs4(v,u,K,max(L,mxd-K),min(R,mxd),tp);
	}
}

int sum[MAXN];

void solve(int u,int K,int L,int R,int op){
	for(int v:G[u]) sum[v]=0;
	Q.clear();
	Q.push_back({L,0}),Q.push_back({R+1,0});
	for(auto i:E[u])
		Q.push_back({max(L,i.first-K),0}),Q.push_back({min(R,i.first)+1,0});
	for(int v:G[u]){
		if(vis[v]) continue;
		dfs4(v,u,K,L,R,v);
	}
	sort(Q.begin(),Q.end());
	ll sum1=0,sum2=0;
	int p=E[u][0].second,q=E[u][1].second;
	for(int i=0;i<(int)Q.size()-1;i++){
		int x=Q[i].first,tp=Q[i].second,Mul=op*(Q[i+1].first-Q[i].first);
		if(x>=R) break;
		if(tp>0) sum2+=sum[tp],sum[tp]++,sum1++;
		if(tp<0) sum[-tp]--,sum1--,sum2-=sum[-tp];
		if(x<=E[u][0].first&&E[u][0].first<=x+K) {
			ans+=1ll*Mul*(sum1-sum[p])*(sum1-sum[p]+1)/2;
			ans-=1ll*Mul*(sum2-1ll*sum[p]*(sum[p]-1)/2);
		}
		if(x<=E[u][1].first&&E[u][1].first<=x+K)
			ans+=1ll*Mul*sum[p]*(sum1-sum[p]-sum[q]+1);
		if(x<=E[u][2].first&&E[u][2].first<=x+K)
			ans+=1ll*Mul*sum[p]*sum[q];
	}
}

void dfs3(int u){
	if(K) solve(u,K-1,1,n-K,-1);
	solve(u,K,0,n-K,1);
	vis[u]=1;
	for(int v:G[u]){
		if(vis[v]) continue;
		Get_siz(v,0);
		rt=-1,Get_rt(v,u,siz[v]);
		dfs3(rt); 
	}
}

int main(){
	freopen("pseudotree.in","r",stdin);
	freopen("pseudotree.out","w",stdout); 
	int ID,Num;
	scanf("%d%d",&ID,&Num);
	while(Num--){
		scanf("%d%d",&n,&K),ans=0;
		FL(i,1,n) G[i].clear(),E[i].clear(),Dw[i]=Up[i]=vis[i]=0; 
		FL(i,1,n-1){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		if(K>=n-1){
			printf("%lld\n",1ll*n*(n-1)/2);
			continue;
		}
		dfs1(1,0);
		dfs2(1,0);
		rt=-1,Get_rt(1,0,n);
		dfs3(rt); 
		printf("%lld\n",ans); 
	}
}

4.23

A

发现无标号且互不相同的方案很难处理，可以转成有标号、允许相同的方案数，有标号就是无标号、互不相同的方案乘个 $n!$ ，互不相同就是允许相同容斥一下。

先考虑一维的情况，假设这一维离散化后有 $s$ 个不同坐标，每条线段选择两个不同坐标作为左右端点，

如果不要求所有坐标都被用到，那么每条线段有 $\binom{s}{2}$ 种选择，于是 $i$ 条有标号线段一共有 $\binom{s}{2}^i$ 种选择。

然后因为要求恰好 $s$ 个，所以考虑容斥，设一维下有 $i$ 条有标号线段，且离散化后恰好有 $s$ 个坐标的方案数为 $a_{i,s}$ ，有：

$$a_{i,s}=\sum_{j=0}^s(-1)^{s-j}\binom{s}{j}\binom{j}{2}^i$$

于是一维下 $i$ 条有标号线段、且允许相同的方案数为：

$$z_i=\sum_{s=1}^{2i}a_{i,s}\\ =\sum_{s=1}^{2i}\sum_{j=1}^s(-1)^{s-j}\binom{s}{j}\binom{j}{2}^i\\ =\sum_{j=1}^{2i}\Big(\sum_{s=j}^{2i}(-1)^{s-j}\binom{s}{j}\Big)\binom{j}{2}^i$$

令 $W_j=\sum_{s=j}^{2n}(-1)^{s-j}\binom{s}{j}$ 。

（为了方便处理上限扩大到 $2n$ 因为当只有 $i$ 条线段的时候 $s>2i$ 对答案是没有贡献的）。

然后我们枚举 $i$ ，每轮令 $W_j\to W_j\cdot \binom{j}{2}$ ，所以第 $i$ 轮时 $\sum W_j$ 就是 $z_i$ 。

此时我们拓展到 $K$ 维，令 $h_i=z_i^K$ ，我们要去掉有重复的方案数。

假设 $i$ 个有标号的物体实际只出现了 $j$ 种不同物体，那么这 $i$ 个标号可以被划分成 $j$ 个非空集合，每个集合中的物体完全相同。

把 $i$ 个标号划分成 $j$ 个非空无序集合的方案数是第二类斯特林数： $\genfrac{\{}{\}}{0pts}{}{i}{j}$ 。

有：

$$h_i=\sum_{j=1}^i\genfrac{\{}{\}}{0pts}{}{i}{j}g_j\\ \Rightarrow g_i=h_i-\sum_{j=1}^{i-1}\genfrac{\{}{\}}{0pts}{}{i}{j}g_j$$

因为 $g_1\sim g_{i-1}$ 已经在之前的轮数算出，所以直接减去即可， $\genfrac{\{}{\}}{0pts}{}{i}{j}$ 可以递推求出。

最后输出 $\dfrac{g_i}{i!}$ 就是答案。

时间复杂度 $\mathcal{O}(n^2+n\log K)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e4 + 10;
const int mod = 998244353;

int n,K;
int fac[MAXN],inv[MAXN];
ll W[MAXN],S[2][MAXN],f[MAXN];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int C(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; 
}

int main(){
	freopen("cube.in","r",stdin);
	freopen("cube.out","w",stdout); 
	scanf("%d%d",&n,&K);
	fac[0]=1;
	FL(i,1,(n<<1)) fac[i]=1ll*fac[i-1]*i%mod;
	inv[(n<<1)]=qpow(fac[(n<<1)],mod-2);
	FR(i,(n<<1)-1,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	FL(i,1,(n<<1)){
		FL(j,i,(n<<1)){
			if((j-i)&1) W[i]=(W[i]-C(j,i)+mod)%mod;
			else W[i]=(W[i]+C(j,i))%mod;
		}
	}
	S[0][0]=1; 
	FL(i,1,n){
		//S[i][j]=S[i-1][j-1]+j*S[i-1][j]
		int nw=i&1;
		S[nw][0]=0; 
		FL(j,1,i) S[nw][j]=(1ll*j*S[nw^1][j]%mod+S[nw^1][j-1])%mod;
		FL(j,1,(n<<1))
			W[j]=1ll*W[j]*((1ll*j*(j-1)/2)%mod)%mod,f[i]=(f[i]+W[j])%mod;
		f[i]=qpow(f[i],K);
		FL(j,1,i-1) f[i]=(f[i]-1ll*f[j]*S[nw][j]%mod+mod)%mod;
		printf("%lld\n",1ll*f[i]*inv[i]%mod);
	}
}

B

原题 QOJ6011

我们设 $L$ 为 $S$ 到 $T$ 的曼哈顿距离， $R$ 为原图中 $S$ 到 $T$ 的最短路长度，显然构造后的最短路一定在 $[L,R]$ 区间里，同时网格图还是一个二分图，所以路径长度的奇偶性是固定的，如果 $D<L\lor D>R\lor D\not\equiv L\pmod2$ ，那么无解。

然后有结论：如果原图是好地图，那么可以不断找到一个可以拆掉的墙，使得拆掉后地图仍然是好地图，并且任意两点之间的最短路最多只会减少 $2$ 。

因为网格图路径长度奇偶性固定，所以 $S$ 到 $T$ 的最短路长度每次只可能不变或者减少 $2$ ，

于是从原始最短路开始，不断拆墙，最短路长度一定会经过 $[L,R]$ 区间内所有和 $L$ 同奇偶的长度，所以我们先找出一种合法的拆墙顺序，然后二分拆到哪里距离恰好为 $D$ 即可。

考虑如何找出一种合法的拆墙顺序，考虑 bfs，我们先把边角的障碍加入然后每次判断能否删除，删除之后更新周边的边角状态。

（关于边角的障碍，也就是有横向空格也有纵向空格相邻的障碍，因为不存在角相邻，所以它一定是孤立点/有相邻的一个障碍/两个障碍，删除大概率不会出现角相邻，我们优先判断）。

时间复杂度 $\mathcal{O}(nm\log (nm))$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e3 + 10;
const int inf = 0x3f3f3f3f;

int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};

int n,m,D;
int sx,sy,ex,ey;
int dis[MAXN][MAXN],tim[MAXN][MAXN];  
char s[MAXN][MAXN],t[MAXN][MAXN];

int bfs(){
	FL(i,1,n) FL(j,1,m) dis[i][j]=inf;
	queue<PII>q;
	dis[sx][sy]=0,q.push({sx,sy});
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();
		FL(i,0,3){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||t[nx][ny]=='#') continue;
			if(dis[nx][ny]>dis[x][y]+1){
				dis[nx][ny]=dis[x][y]+1;
				q.push({nx,ny});
			}
		}
	}
	return dis[ex][ey];
}

bool Val(int x,int y){
	if(x<1||x>n||y<1||y>m||s[x][y]!='#') return 0;
	return ((s[x][y-1]!='#'||s[x][y+1]!='#')&&(s[x-1][y]!='#'||s[x+1][y]!='#'));
}

bool Chk(int x,int y){
	if(s[x][y]!='#') return 0;
	if(s[x-1][y]=='#'&&s[x][y-1]=='#'&&s[x-1][y-1]!='#') return 0;
	if(s[x+1][y]=='#'&&s[x][y-1]=='#'&&s[x+1][y-1]!='#') return 0;
	if(s[x-1][y]=='#'&&s[x][y+1]=='#'&&s[x-1][y+1]!='#') return 0;
	if(s[x+1][y]=='#'&&s[x][y+1]=='#'&&s[x+1][y+1]!='#') return 0;
	return 1;
}

int main(){
	freopen("map.in","r",stdin);
	freopen("map.out","w",stdout); 
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d%d",&n,&m,&D);
		int idx=0;
		FL(i,0,n+1) FL(j,0,m+1) tim[i][j]=inf;
		FL(i,0,n+1){
			scanf("%s",s[i]);
			FL(j,0,m+1){
				t[i][j]=s[i][j];
				if(s[i][j]=='S') sx=i,sy=j;
				if(s[i][j]=='T') ex=i,ey=j;
				idx+=(i>=1&&i<=n&&j>=1&&j<=m&&s[i][j]=='#');
			}
		}
		int L=abs(sx-ex)+abs(sy-ey),R=bfs();
		if(D<L||D>R||((D-L)&1)){
			puts("NO");
			continue;
		}
		queue<PII>q; 
		FL(i,1,n)
			FL(j,1,m)
				if(Val(i,j)) q.push({i,j});
		int nw=idx;
		while(!q.empty()){
			int x=q.front().first,y=q.front().second;
			q.pop();
			if(!Chk(x,y)) continue;
			s[x][y]='.',tim[x][y]=nw,nw--;
			FL(i,0,3){
				int nx=x+dx[i],ny=y+dy[i];
				if(Val(nx,ny)) q.push({nx,ny});
			}
		}
		int l=nw,r=idx; 
		while(l<=r){
			int mid=(l+r)>>1;
			FL(i,1,n)
				FL(j,1,m)
					t[i][j]=((s[i][j]=='#'||(s[i][j]=='.'&&tim[i][j]<=mid))?'#':'.');
			t[sx][sy]='S',t[ex][ey]='T';
			int nw=bfs();
			if(nw==D){
				puts("YES"); 
				FL(i,0,n+1){
					FL(j,0,m+1)
						printf("%c",t[i][j]);
					puts("");
				}
				break;
			}
			if(nw<D) l=mid+1;
			else r=mid-1;
		}
	}
	return 0;
}

C

原题 QOJ5404

考虑满二叉树的情况，我们很容易判断一个点是不是叶子，我们询问 $[n]/\{i\}$ ，

如果 $i$ 不是叶子，那么它一定能被它的两个儿子的 $\mathrm{lca}$ 生成出来，答案 $=n$ ，否则 $i$ 不能被生成，答案 $=n-1$ 。

于是我们找到了一批叶子节点，不妨设集合为 $L$ ，然后我们想找某个叶子 $u$ 的父亲，考虑用 $L/\{u\}$ 生成虚树，根据满二叉树的定义，此时除了 $u$ 之外，唯一缺失的内部点就是 $u$ 的父亲，而当一个非叶子节点的两个儿子都已经确定，我们可以将它的两个儿子删去，将其视为新的叶子节点。

考虑如何找到 $u$ 的父亲，对于 $u$ ，有一个可用父亲集合 $V$ ，满足其不是叶子节点，也不在 $u$ 确定的子树里，然后还没有确定 $2$ 个儿子，对 $V$ 二分即可（即询问 $V$ 的前缀，找到最早使得虚数大小达到目标值的位置，就是 $u$ 的父亲）。

这样我们就从下往上还原了这棵树。

考虑拓展到一般情况，我们称只有一个儿子的节点为 $1$ 度点，考虑有 $1$ 度点的时候，对于 $1$ 度点 $i$ ，询问 $[n]/\{i\}$ 的答案也是 $n-1$ （它无法作为它的儿子的 $\mathrm{lca}$ 被加入虚树），所以我们无法通过这个区分 $1$ 度点和叶子节点。

我们把在上述询问答案为 $n-1$ 的点拉出来，发现我们可以通过询问所有叶子和 $1$ 度点的集合去掉点 $i$ 来判断 $i$ 是否是 $1$ 度点，如果询问的答案是 $n-1$ 那么 $i$ 是 $1$ 度点（因为 $i$ 的父亲不会被 $i$ 的状态影响），否则答案是 $n-2$ 那么 $i$ 是叶子节点。

此时我们把非 $1$ 度点的点按照满二叉树的做法做，建出骨架树，此时 $1$ 度点会插入在骨架树的边上。

如果要确定原树，那么要求骨架上一条边不能插入超过 $1$ 个 $1$ 度点，因为如果有 $>1$ 个 $1$ 度点，这些点任意交换顺序询问结果不变，原树不唯一，无解。

考虑找到骨架树中 $x$ 插入的位置。

如果 $2$ 度点是链就可以直接二分，询问链的前缀，把不在链上的儿子和 $x$ 做询问，找第一个和 $x$ 有祖先关系的点。

考虑对于一个点 $x$ 和点集 $S$ 可以询问出什么，保证 $S$ 集合中的点均没有祖先关系，为一条链上每个点不在链上的儿子组成的集合，此时如果 $x$ 与 $S$ 中的点均没有祖先关系，也就是不在链上这段前缀的负责范围，那么询问答案就是 $2|S|+1$ ，和 $x$ 有 $|S|$ 个不同的 $\mathrm{lca}$ ，否则 $x$ 和 $S$ 中点有祖先关系。

然后拓展到树就是我们树剖一下，在重链上二分，同样询问链的前缀，把前缀每一个点的轻儿子和 $x$ 做询问，判断和 $x$ 的祖先关系，如果有 $x$ 的祖先那么 $x$ 的插入位置就在当前重链前半段负责的范围内（可能是重链上的边也可能是轻子树内的边），否则在继续往下二分。

然后我们这里用 $siz$ 记录一个子树内还可以插入 $1$ 度点的边数，把所有在重儿子子树外有可插入边的分岔点拉出来，每次找使得两部分 $siz$ 尽可能平均的分岔点进行询问，就是全局平衡二叉树做带权二分。

此时询问次数 $\mathcal{O}(\log n)$ 。

此时我们找到 $x$ 属于的分岔点 $v$ ，判断 $x$ 和 $v$ 的重儿子 $ls_v$ 是否有祖先关系，如果有那么 $x$ 在 $fa_v\to v$ 的边上（这里注意判断，如果 $v$ 不是当前递归重链的起点 $u$ ，并且 $v$ 与父亲 $fa_v$ 之间没有被任何可插入位置区分开，且 $x$ 可以被插入在 $[u,fa_v]$ ，此时原树不唯一，是无解的），否则 $x$ 在 $v$ 的轻儿子 $rs_v$ 的子树里，继续递归，然后有一个剪枝，如果 $siz_{rs_v}=0$ 那么肯定无法放置，直接返回无解。

注意如果骨架树的根不是 $1$ ，那么说明 $1$ 只有 $1$ 个儿子，把 $1$ 连向 $rt$ 。

时间复杂度 $\mathcal{O}(n^2\log n)$ ，实际询问次数最坏是 $2n+2n\log n$ 。

#include"oracle.h"
#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e3 + 10;

int n,m,rt=-1,cnt=0;
int fa[MAXN],siz[MAXN],id[MAXN];
int ls[MAXN],rs[MAXN];
int a[MAXN],l,r;
vector<int>G[MAXN];
int vis[MAXN];
bool lf[MAXN],ch[MAXN];

void dfs1(int u,int tim){
	vis[u]=tim;
	for(int v:G[u]) dfs1(v,tim);
}

void dfs2(int u){
	siz[u]=!lf[u]&&!id[u];
	if(G[u].empty()) return ;
	ls[u]=G[u][0],rs[u]=G[u][1];
	dfs2(ls[u]),dfs2(rs[u]);
	siz[u]+=siz[ls[u]],siz[u]+=siz[rs[u]]; 
	if(siz[ls[u]]<siz[rs[u]]) swap(ls[u],rs[u]);
}
bool Qry(int x,int u,int nw){
	vector<int>S;
	S.push_back(rs[u]);
	S.push_back(nw);
	while(x!=u){
		S.push_back(rs[x]);
		x=fa[x];
	}
	return (query(S)<=(2*((int)S.size()-1)));
}
bool find(int u,int nw){
	if(!siz[u]) return 0;
	l=1,r=0;
	int x=u;
	while(!lf[x]){
		if(siz[x]>siz[ls[x]]) a[++r]=x;
		x=ls[x];
	}
	a[l-1]=a[r+1]=0;
	while(l<r){
		int p=l;
		FL(i,l+1,r-1)
			if(max(siz[a[l]]-siz[a[i+1]],siz[a[i+1]]-siz[a[r+1]])<max(siz[a[l]]-siz[a[p+1]],siz[a[p+1]]-siz[a[r+1]])) p=i;
		if(Qry(a[p],u,nw)) r=p;
		else l=p+1;
	}
	int v=a[l];
	if(query({nw,ls[v]})==2){
		if(id[v]||((v!=u&&siz[v]==siz[fa[v]])&&Qry(fa[v],u,nw))) return 0;
		id[v]=nw;
		return 1;
	}
	if(G[rs[v]].empty()) return 0;
	return find(rs[v],nw);
}

void solve(int N,int Id){
	n=N,m=n,cnt=0;
	FL(i,1,n) fa[i]=siz[i]=id[i]=vis[i]=lf[i]=ch[i]=0,G[i].clear();
	FL(i,1,n){
		vector<int>S;
		FL(j,1,n) if(j!=i) S.push_back(j);
		if(query(S)<n) lf[i]=1;
	}
	FL(i,1,n){
		if(!lf[i]) continue;
		vector<int>S;
		FL(j,1,n) if(j!=i&&(lf[j]||ch[j])) S.push_back(j);
		if(query(S)==n-1) lf[i]=0,ch[i]=1,m--;
	}
	queue<int>q;
	FL(i,1,n)
		if(lf[i]) q.push(i),cnt++;
	if((cnt<<1)!=m+1){
		report(0,0);
		return ;
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		dfs1(u,u);
		int nw=m-count(vis+1,vis+n+1,u);
		vector<int>V;
		FL(i,1,n)
			if(!lf[i]&&!ch[i]&&vis[i]!=u&&G[i].size()<2) V.push_back(i);
		if(V.empty()){
			rt=u;
			break;
		}
		int Siz=(int)V.size(),ps=Siz-1;
		FR(j,19,0){
			if((1<<j)>ps) continue;
			vector<int>S;
			FL(i,1,n)
				if(lf[i]&&vis[i]!=u) S.push_back(i);
			FL(i,0,ps-(1<<j))
				S.push_back(V[i]);
			if(query(S)==nw) ps-=(1<<j);
		}
		fa[u]=V[ps],G[fa[u]].push_back(u);
		if((int)G[fa[u]].size()==2) q.push(fa[u]);
	}
	assert(rt!=-1);
	if(rt!=1) fa[rt]=1;
	FL(i,2,n){
		if(!ch[i]) continue;
		dfs2(rt);
		if(!find(rt,i)){
			report(0,0);
			return ;
		}
	}
	FL(i,1,n) if(id[i]) fa[id[i]]=fa[i],fa[i]=id[i];
	FL(i,1,n) if(fa[i]) report(fa[i],i);
}

4.24

A

首先令每个数 $a_i\to M-a_i$ ，那么变成 $a_i>0$ 时 $−1$ 或删除一个数。

考虑按照正数的个数分讨，我们设有 $z$ 个 $0$ ，正数为 $x_1,\cdots,x_k$ ，记博弈状态为 $[z,(x_1,\cdots,x_k),A/B]$ 。

首先发现如果 $[z,(x_1,\cdots,x_k),A]$ bob 必胜那么 $[z+3,(x_1,\cdots,x_k),A]$ bob 也必胜，因为我们把前三个 $0$ 分为 $1$ 组，当 Alice 删除了其中 $1$ 个，bob 可以删除另外 $2$ 个使得状态变成前者。

考虑 $k=0$ ，对于 $[z,(),A]$ 显然有 $z\equiv 1/2\pmod 3$ 时 Alice 必胜， $z\equiv 0\pmod 3$ 时 bob 必胜。

然后考虑 $k=1$ ：

考虑比较简单的 $[z,(x_1),B]$ ，bob 可以选择：

删除 $2$ 个 $0$ ：变为 $[z-2,(x_1),A]$
删除 $x_1$ 和 $0$ ：变为 $[z-1,(),A]$ 。
对 $x_1$ 减 $1$ 再删除 $x_1$ ：变为 $[z,(),A]$ 。
将 $x_1$ 减 $2$ ：变为 $[z,(x_1-2),A]$ 。

发现当 $z\not\equiv2\pmod 3$ 的时候，bob 可以获胜，否则看 $[z-2,(x_1),A],[z,(x_1-2),A]$ 的胜负。

然后考虑 $[z,(x_1),A]$ 时 Alice 的决策，

如果 $z\not\equiv 2\pmod 3$ ，那么 Alice 可以直接删除 $x_1$ 得到必胜态。
否则 $z\equiv 2\pmod 3$ ，Alice 只能选择转移到 $[z,(x_1-1),B]$ ，此时 bob 也一定不会在 $x_1-1>0$ 的情况下去操作 $z$ 或者删除 $x_1$ ，把必胜态送给给对手，因为 bob 最多能让 $z$ 变化 $2$ ，无法让 $z$ 重新变化为 $z\equiv2\pmod 3$ 。

（转移到 $[z-2,(x_1-1),A]/[z-1,(),A]$ 显然都不优，因为都是 Alice 的必胜态）

所以 $x_1$ 以 $3$ 为周期变化，当 $x_1\equiv 1\pmod 3$ 时转移到 $[z+1,(),B]$ ，这个是 bob 的必败态，Alice 的必胜态，当 $x_1\equiv 2\pmod 3$ 时可以转移到 $[z,(x_1-1),B]$ ， $B$ 只能选择转移到 $[z,(),A]$ ，这是 Alice 的必胜态。

所以 $[z,(x_1),A]$ Alice 必胜当且仅当 $z\not\equiv2\pmod 3\lor x_1\not\equiv0\pmod 3$ ，结合上面的分析， $[z,(x_1),B]$ Alice 必胜当且仅当 $z\equiv 2\pmod 3\land x_1\not\equiv 2\pmod 3$ 。

继续考虑 $k=2$ ，设 $x_1\le x_2$ ：

观察到对于 $[z,(x_1,x_2),A]$ ，且 $z\equiv0\pmod 3$ ，Alice 一定必败，是 bob 的必胜态。

如果 Alice 删除 $1$ 个 $0$ ，bob 删除 $2$ 个 $0$ 可以递归到 $[z-3,(x_1,x_2),A]$ ，继续解决同类状态。
否则如果 Alice 对 $x_1/x_2$ 进行操作，bob 可以用 $2$ 次操作将 $x_1,x_2$ 都删掉递归到 $[z,(),A]$ ，这个是 bob 的必胜态。

然后推广到 $[z,(x_1,x_2),B]$ 均为 bob 的必胜态，

若 $z\equiv 0\pmod 3$ ，bob 删除 $x_1,x_2$ 转移到 $[z,(),A]$ ，这个是 Alice 的必败态，也是 bob 的必胜态。
若 $z\equiv 1\pmod 3$ ：
- 若有 $x_2>1$ ，那么转移到 $[z-1,(x_1,x_2-1),A]$ 是 bob 的必胜态。
- 否则 $x_1=x_2=1$ ，那么令 $x_1\to x_1-1,x_2\to x_2-1$ ，转移到 $[z+2,(),A]$ ，依旧是 bob 的必胜态。
若 $z\equiv 2\pmod 3$ ：

删除 $2$ 个 $0$ 转移到 $[z-2,(x_1,x_2),A]$ 是 bob 的必胜态。

然后考虑 $[z,(x_1,x_2),A]$ ，对于 $z\not\equiv 0\pmod 3$ ，Alice 想赢只能让 $k$ 变小：

若 $z\equiv 1\pmod 3$ ：

Alice 可以删除一个数转移到 $[z,(x_1),B]$ ， $z\equiv 1\pmod 3$ ，是 bob 的必胜态。
那么如果 $x_1=1$ ，Alice 令 $x_1\to x_1-1$ ，转移到 $[z+1,(x_2),B]$ ，当 $x_2\not\equiv 2\pmod 3$ 时 Alice 必胜。

若 $z\equiv 2\pmod 3$ ：

Alice 删除一个数转移到 $[z,(x_1),B]$ ，只要存在 $x_1/x_2\not\equiv 2\pmod 3$ ，Alice 可以获胜。

然后对于 $k\ge 3$ 归纳一下可以得到此时 bob 必胜。

然后按公式计算即可，时间复杂度 $\mathcal{O}(n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e6 + 10;
const int mod = 998244353;

int n,ans=0;
int cnt[MAXN],tot[3],sum=0;
int fac[MAXN],inv[MAXN];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int C(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d",&n);
	fac[0]=1;
	FL(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2);
	FR(i,n-1,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	FL(i,1,n){
		int x;
		scanf("%d",&x);
		cnt[x]++;
	}
	string St;
	cin>>St;
	if(St=="Alice"){
		FL(i,1,n){
			for(int j=1;j<=cnt[i];j+=3)
				ans=(ans+1ll*C(cnt[i],j)*(1+sum+1ll*cnt[i-1]*(tot[0]+tot[1])%mod-1ll*cnt[i-1]*(cnt[i-1]+1)/2%mod)%mod)%mod;
			for(int j=2;j<=cnt[i];j+=3)
				ans=(ans+1ll*C(cnt[i],j)*((1+tot[1]+tot[2]+1ll*sum*(sum-1)/2%mod-1ll*tot[2]*(tot[2]-1)/2%mod)%mod+mod)%mod)%mod;
			for(int j=3;j<=cnt[i];j+=3)
				ans=(ans+1ll*C(cnt[i],j)*sum%mod)%mod;
			tot[0]+=cnt[i],sum+=cnt[i];
			swap(tot[0],tot[2]),swap(tot[1],tot[2]);
		}
		printf("%d\n",ans);
	}
	else{
		FL(i,1,n){
			for(int j=1;j<=cnt[i];j+=3)
				ans=(ans+C(cnt[i],j))%mod;
			for(int j=3;j<=cnt[i];j+=3)
				ans=(ans+C(cnt[i],j))%mod;
			for(int j=2;j<=cnt[i];j+=3)
				ans=(ans+1ll*C(cnt[i],j)*(tot[0]+tot[1])%mod)%mod;
			tot[0]+=cnt[i];
			swap(tot[0],tot[2]),swap(tot[1],tot[2]);
		}
		printf("%d\n",((qpow(2,n)-1-ans)%mod+mod)%mod);
	}
}

B

原题 P8004

不妨设原树和新树都以 $1$ 为根，定义每个点的度数为此时的儿子数，发现可以将传送门视作将一个点的出边改变连接的节点，且最多只需要 $n-1$ 对传送门，不会受到 $L$ 的限制。

（具体地，对于两条边 $(f_{u},u),(f_v,v)$ ，在 $(f_u,u)$ 上放正面朝 $u$ 的传送门，在 $(f_v,v)$ 上放正面朝 $f_v$ 的传送门，那么相当于变成了 $(f_u,v),(f_v,u)$ ）。

对于新树，只要树中的每个节点在新树中的度数相同那么就是可以达成的，我们希望最小化黑点的深度之和。

首先考虑特殊性质，如果原树的所有叶子节点都是黑点，发现我们按照度数从大到小依次放置白点一定是最优的。

（如果白点有一个度数比它小的祖先，如果交换它们，只有它们的直系儿子的深度会改变，显然把这个点换上去放在更浅的层的点数会变多）。

然后我们拓展到平凡情况，就是我们会发现，所有黑点一定是挂在按照度数排序的点（有黑也有白，单纯按度数排序，如果度数相同黑点在前）的一个前缀上，我们并不关心除了这个前缀内的白点之外的白点。

换句话说，白点的放置是最优的当且仅当它的所有祖先的度数都大于它或者它的子树内没有黑点。

于是我们直接排序并放置每个点是 $\mathcal{O}(n^2)$ 的。

我们设按度数排序后所有节点的序列为 $a$ ，按度数排序后黑点的序列为 $b$ 。

考虑优化，发现放置一个点是无法优化的，但是我们可以每次放置一层点（在 $a$ 中这是一段连续的区间），发现对于儿子数 $\ge 2$ 的点，它们的下一层的点数至少是这一层点数的 $2$ 倍。

于是这样的点最多只有 $\mathcal{O}(\log n)$ 层，然后剩下的点是挂在最后一层下形成若干条链（因为儿子数 $\le 1$ ），于是我们枚举这个前缀分界点 $Ps$ ，每个前缀 $\mathcal{O}(\log n)$ 计算，时间复杂度 $\mathcal{O}(n\log n)$ 。

考虑具体计算，

为了方便表述，令 $deg_i$ 表示 $i$ 点的儿子个数，$sa_i=\sum_{j=1}^i deg_{a_j},sb_i=\sum_{j=1}^i deg_{b_j}$， $cnt_i$ 表示 $a_1\sim a _i$ 中的黑点数量。

固定 $Ps$ 后，放置顺序是 $a_2,a_3,\cdots,a_{Ps},b_{cnt_{Ps}+1}\cdots b_{m}$ ，剩下的白点我们并不关心。

我们记录当前放置了 $l$ 个点，当前层可以放置的点数 $lcnt$ ，

那么当我们新增当前层，所有未被放置的黑点深度 $+1$ ，这一层对答案的贡献为 $m-cnt_l$ 。

若 $l+lcnt\le Ps$ ，那么这层会放置 $a_{l+1}\sim a_{l+lcnt}$ ，下一层可以放置的点数就是 $sa_{l+lcnt}-sa_{l}$ 。
否则这层会放置 $a_{l+1}\sim a_{Ps},b_{cnt_{Ps}+1}\sim b_{cnt_{Ps}+((l+lcnt)-Ps)}$。

此时一共放置了 $r=cnt_{Ps}+((l+lcnt)-Ps)$ 个黑点。

然后和前面的放置是同理的，记录当前层可以放置的黑点点数 $rcnt$ ，直到 $r+rcnt>m$ ，每一层对答案的贡献都是 $m-r$ 。

然后一些细节：

如果 $lcnt=0/rcnt=0$ 且此时没有放置完所有点那么无解。

如果这一层已经全是一个儿子的了，那我们可以 $\mathcal{O}(1)$ 计算，此时我们只会挂黑点，假设我们要挂 $b_{id+1}\sim b_{m}$ 的黑点，有 $cnt$ 条链可以挂。

若 $0$ 度点的数量 $(m-id)-(sb_{m}-sb_{id})\ge cnt$ 那么无解，否则构造 $(m-id)=k\cdot cnt+t$ ，有 $0\cdot cnt+1\cdot cnt+\cdots+(k-1)cnt+kt=\frac{k(k-1)}{2}cnt+kt$。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f; 

int n,m,L;
ll ans;
int num,tot=0;
int deg[MAXN];
int a[MAXN],b[MAXN];
int sa[MAXN],sb[MAXN],cnt[MAXN];
int fa[MAXN],f[MAXN];
int eid[MAXN],p[MAXN];
PII e[MAXN];
vector<PII>G[MAXN],E[MAXN],Q[MAXN];
vector<int>G1[MAXN],G2[MAXN];
bool val[MAXN];

bool cmp(int p,int q){
	if(deg[p]!=deg[q]) return (deg[p]>deg[q]);
	return val[p]>val[q];
}

void dfs(int u,int fth){
	f[u]=fth;
	for(auto i:G[u]){
		int v=i.first,id=i.second;
		if(v==fth) continue;
		E[u].push_back({v,id}),eid[v]=id;
		dfs(v,u);
	}
	deg[u]=(int)E[u].size();
}

ll Get(int ps,int cnt){
	if(((m-ps)-(sb[m]-sb[ps]))>=cnt) return inf;
	ll rem=(m-ps),k=rem/cnt,t=rem%cnt;
	return 1ll*k*(k-1)/2*cnt+k*t; 
}

ll Calc(int Ps){
	ll res=0;
	int l=1,lcnt=deg[1];
	while(l+lcnt<=Ps){
		res+=(m-cnt[l]);
		if(!lcnt) return (l==n?res:inf);
		if(Ps<n&&l!=1&&deg[a[l+1]]<=1) return res+Get(cnt[l],lcnt); 
		int ncnt=sa[l+lcnt]-sa[l];
		l+=lcnt,lcnt=ncnt;
	}
	res+=(m-cnt[l]);
	int r=cnt[Ps]+lcnt-(Ps-l),rcnt=(sb[r]-sb[cnt[Ps]])+(sa[Ps]-sa[l]);
	if(r>m) return res;
	while(r+rcnt<=m){
		res+=(m-r);
		if(!rcnt) return (r==m&&(n-Ps==m-cnt[Ps])?res:inf);
		if(Ps<n&&deg[b[r+1]]<=1) return res+Get(r,rcnt); 
		int ncnt=sb[r+rcnt]-sb[r];
		r+=rcnt,rcnt=ncnt;
	}
	res+=(m-r);
	return res;
}

void Swp(int u,int v){
	tot++;
	Q[eid[u]].push_back({tot,1});
	Q[eid[v]].push_back({tot,0});
	swap(p[u],p[v]);
}

int main(){
    freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d%d",&n,&m,&L);
		FL(i,1,n) G[i].clear(),G1[i].clear(),G2[i].clear(),E[i].clear(),Q[i].clear(),f[i]=fa[i]=val[i]=0;
		FL(i,1,n-1){
			int u,v;
			scanf("%d%d",&u,&v);
			e[i]={u,v};
			G[u].push_back({v,i});
			G[v].push_back({u,i});
		}
		FL(i,2,n) a[i]=i;
		FL(i,1,m){
			int x;
			scanf("%d",&x);
			val[x]=1;
		}
		dfs(1,0);
		sort(a+2,a+n+1,cmp);
		int idx=0;
		FL(i,2,n){
			cnt[i]=cnt[i-1]+val[a[i]];
			if(val[a[i]]) b[++idx]=a[i];
		}
		FL(i,1,n) sa[i]=sa[i-1]+deg[a[i]];
		FL(i,1,m) sb[i]=sb[i-1]+deg[b[i]]; 
		ans=Calc(n),num=n;
		FL(i,1,n-1){
			ll now=Calc(i);
			if(now<ans) ans=now,num=i; 
		}
		printf("%lld\n",ans); 
		queue<int>q;
		FL(i,1,deg[1]) q.push(1);
		FL(i,2,num){
			int u=a[i];
			fa[u]=q.front();
			q.pop();
			FL(j,1,deg[u]) q.push(u);
		}
		FL(i,1,m){
			int u=b[i];
			if(fa[u]) continue;
			fa[u]=q.front();
			q.pop();
			FL(j,1,deg[u]) q.push(u);
		}
		FL(i,num+1,n){
			int u=a[i];
			if(fa[u]) continue;
			fa[u]=q.front();
			q.pop();
			FL(j,1,deg[u]) q.push(u);
		}
		FL(i,2,n) G1[f[i]].push_back(i),G2[fa[i]].push_back(i);
		FL(i,1,n)
			for(int j=0;j<(int)G1[i].size();j++) p[G1[i][j]]=G2[i][j];
		tot=0;
		FL(i,2,n)
			while(i!=p[i]) Swp(i,p[i]);
		FL(i,1,n-1){
			int u=e[i].first,v=e[i].second;
			if(v==f[u]){
				reverse(Q[i].begin(),Q[i].end());
				for(auto &j:Q[i]) j.second=1-j.second;
			}
			printf("%d ",(int)Q[i].size());
			for(auto j:Q[i]) printf("%d %d ",j.first,j.second);
			puts("");
		}
	} 
}

省集笔记（4.20~4.24）

4.20

A

B

4.21

A

B

C

4.23

A

B

C

4.24

A

B

Status

Development

Support

About

省集笔记（4.20~4.24）

4.20

A

B

4.21

A

B

C

4.23

A

B

C

4.24

A

B

Status

Development

Support

About

SIGN IN