【省选做题】[省选联考 2022] 填树
小木虫
·
·
题解
Preface
希望这篇题解能够帮助和我一样的计数蒟蒻。
Problem
给你一棵 n 个节点的树，每个点 i 可以填一个 [l_i,r_i] 以内的权值，也可以不填，现在我们要填一条树上路径，要求这条路径上的权值极差在 k 以内，问有多少种方案以及所有方案的权值和为多少。
### Solution
**算法1（10pts）：**
我们发现我们可以爆枚每一个节点的权值，然后判断合法，这样可以通过第一个测试点，期望得分 10 分。
**算法2（20pts）**
我们发现这个问题应当是可以 dp 的，但是无法绕开权值的限制，那我们就先依赖权值写一个 dp，我们暴力枚举我们要选的路径的最小值 $x$，那么每个点的合法点权就在 $[x,x+k]$ 内，然后进行树上 dp，发现我们还需要钦定某些点为最小值，不然会算出某些最小值大于 $x$ 的答案，但如果直接钦定的话我们的复杂度又会退化为爆搜，正难则反，考虑删掉最小值大于 $x$ 的答案，即合法点权在 $[x+1,x+k]$ 内的方案，这部分直接动规掉就好，然后我们获得了一个复杂度 $O(nV)$ 的算法，期望得分 20 分。
这部分的动规可能要进行一些介绍，我认为还是不算送分的。
设 $dp1_u$ 为 $u$ 子树内的总方案数，$cdp1_u$ 为 $u$ 子树内，且填的数形成一条以 $u$ 为一个端点的链的总方案数，$dp2_u$ 为 $u$ 子树内的总权值和，$cdp2_u$ 同理。
先来写较为简单的部分：
设 $w$ 为节点 $u$ 上的合法区间大小，$left$ 为合法区间的左端点，$right$ 为右端点，依照上文可知 $[left,right]=[x,x+k]\cap [l_u,r_u]$。
$$cdp1_u=w+\sum_{v\in son_u}cdp1_v\times w$$
$$
\begin{array}{rcl}
cdp2_u&=&(\frac{w\times(w+1)}{w}+(left-1)\times w)\\
&+&\sum_{v\in son_u}cdp2_v\times w\\
&+&(\frac{w\times(w+1)}{2}+(left-1)\times w)\times cdp1_v
\end{array}
$$
其中第一个柿子较好理解，第二个柿子就是把点 $u$ 的贡献与 $v$ 子树的贡献分开计算了，前面都要加一个柿子是因为可以从该点开始。
接下来我们来看较难的部分：
$$dp1_u=w+\sum_{v\in son_u}(1+\sum_{pre} cdp1_{pre})\times cdp1_v \times w$$
$$
\begin{array}{rcl}
dp2_u&=&(\frac{w\times(w+1)}{2}+(left-1)\times w)\\
&+&\sum_{v\in son_u}(1+\sum_{pre} cdp1_{pre})(cdp2_v\cdot w+ (\frac{w(w+1)}{2}+w(left-1))\cdot cdp1_v)\\
&+&(\sum_{pre} cdp2_{pre})\times cdp1_v \times w
\end{array}
$$
$pre$ 代表之前枚举过的 $v$。
第一个柿子同样较好理解，就是将两个链的贡献拼在了一起，乘上了节点本身的贡献。
第二个柿子要分成三部分理解，第一部分为计算 $v$ 子树内向上的贡献，第二部分计算 $u$ 本身的贡献，第三部分计算之前的 $v$ 对现在 $v$ 的贡献。
容易发现内层求和符号可以被前缀和优化，然后单次 dp 即为线性。
**算法3（100pts）**
发现这个问题中的权值不能采用常规手段简单地消去，于是我们转而关注这个问题本身的性质。
经过手玩 $[x,x+k]$ 的滑动窗口，我们发现大部分时候所有的 $[left,right]$ 都在平滑地移动，即左端点或右端点变化 1，而在 $O(n)$ 个关键点处会有一些转折和改变，即变化的端点变化，变化的正负性变化。
这意味着什么？
段数很少，所以我们首先关注一下段内的情况。
树上问题不好分析，所以我们先简化问题，只关注选一条链的情况。
算法 2 中的 dp 在一个链上，如果强制去选这个链的全部的话其实计算出方案数的就是：
$$\prod_{i=1}^{n}(right-left+1)$$
而权值和即为：
$$\sum_{i=1}^n (\frac{w\times(w+1)}{2}+(left-1)\times w)\times (\prod_{j\neq i}^n (right-left+1))$$
发现 $x$ 在段内滑动时，$(right-left+1)$ 为关于 $x$ 的一次函数，$(\frac{w\times(w+1)}{2}+(left-1)\times w)$ 为关于 $x$ 的二次函数。
那么前面两个柿子即为关于 $x$ 的 $n$ 次多项式和关于 $x$ 的 $n+1$ 次多项式。
推广回树上，由于是累加起来的，所以不影响次数，故两个答案依旧分别为对应次数的多项式。
我们发现在每一段内答案都是多项式，我们想求的是每一段内答案的总和，即前缀和的最后一个，而 $m$ 次多项式的前缀和为 $m+1$ 次多项式，那么我们先在每一段内找前 $n+3$ 个点进行暴力 dp 的计算，把他们做前缀和，我们就获得了在一段内答案的前缀和函数的 $n+3$ 个点值，应用拉格朗日插值法我们可以获得这个函数在任意点的取值，也就能获得段内答案总和，复杂度 $O(n)$。
最终总体复杂度 $O(n^3)$，瓶颈在于暴力求点值。
code：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
const int mod=1e9+7;
int n,l[N],r[N],k,num[N*4],tot;
int f[N],g[N],u,v;
vector <int> edge[N];
namespace DP{
int dp1[N],cdp1[N],dp2[N],cdp2[N],vis[N];
bool dfs(int u,int fa,int L,int R){
int left=max(L,l[u]);
int right=min(R,r[u]);
if(left>right)return false;
vis[u]=1;int w=right-left+1;
dp1[u]=cdp1[u]=w;
dp2[u]=cdp2[u]=(w*(w+1)/2+(left-1)*w)%mod;
int sum1=1,sum2=0;
for(auto v:edge[u]){
if(v==fa)continue;
if(!dfs(v,u,L,R))continue;
cdp1[u]+=cdp1[v]*w;
cdp2[u]+=cdp2[v]*w%mod+(w*(w+1)/2+(left-1)*w)%mod*cdp1[v]%mod;
cdp1[u]%=mod;cdp2[u]%=mod;
dp1[u]+=(sum1*cdp1[v]%mod)*w%mod;
dp2[u]+=(cdp2[v]*sum1%mod*w%mod+(w*(w+1)/2+(left-1)*w)%mod*sum1%mod*cdp1[v]%mod+sum2*w%mod*cdp1[v]%mod)%mod;
sum1+=cdp1[v];sum1%=mod;
sum2+=cdp2[v];sum2%=mod;
dp1[u]+=dp1[v];dp2[u]+=dp2[v];
dp1[u]%=mod;dp2[u]%=mod;
}
return true;
}
pair <int,int> solve(int L,int R){
memset(vis,0,sizeof(vis));
int tmp1=0,tmp2=0;
for(int i=1;i<=n;i++){
if(!vis[i]&&(dfs(i,0,L+1,R))){
tmp1+=dp1[i];tmp2+=dp2[i];
tmp1%=mod;tmp2%=mod;
}
}
memset(vis,0,sizeof(vis));
int sum1=0,sum2=0;
for(int i=1;i<=n;i++){
if(!vis[i]&&(dfs(i,0,L,R))){
sum1+=dp1[i];sum2+=dp2[i];
sum1%=mod;sum2%=mod;
}
}
return make_pair((sum1-tmp1+mod)%mod,(sum2-tmp2+mod)%mod);
}
}
int pre[N],suf[N],fac[N],inv[N];
int qpow(int a,int b){
a%=mod;int res=1;
while(b){
if(b&1)res=(1ll*res*a)%mod;
b>>=1;a=(1ll*a*a)%mod;
}return res;
}
int Lag(vector <int> &y,int k){
int res=0,sz=y.size()-1;
if(k<=sz)return y[k];
fac[0]=1;pre[0]=k,suf[sz]=(k-sz+mod)%mod;
for(int i=1;i<=sz;i++){
fac[i]=fac[i-1]*i%mod;
pre[i]=(pre[i-1]*(k-i)%mod+mod)%mod;
}
inv[sz]=qpow(fac[sz],mod-2);
for(int i=sz-1;i>=0;i--)
inv[i]=(inv[i+1]*(i+1))%mod;
for(int i=sz-1;i>=0;i--)
suf[i]=(suf[i+1]*(k-i)%mod+mod)%mod;
int neg=0;
for(int i=0;i<=sz;i++){
int t=y[i];
t*=((i>0?pre[i-1]:1)*(i<sz?suf[i+1]:1)%mod);t%=mod;
t*=(inv[i]*inv[sz-i]%mod);t%=mod;
if((sz-i)&1)res+=mod-t,res%=mod;
else res+=t,res%=mod;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("tree3.in","r",stdin);
cin>>n>>k;int maxV=0;
for(int i=1;i<=n;i++)
cin>>l[i]>>r[i],maxV=max(maxV,r[i]);
for(int i=1;i<n;i++){
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
num[++tot]=1;
num[++tot]=maxV+1;
for(int i=1;i<=n;i++){
num[++tot]=l[i];
if(r[i]<1e9)num[++tot]=r[i]+1;
if(l[i]>k)
num[++tot]=l[i]-k;
if(r[i]>=k)
num[++tot]=r[i]-k+1;
}
sort(num+1,num+1+tot);
int sz=unique(num+1,num+1+tot)-num-1;
int res1=0,res2=0;
for(int i=1;i<sz;i++){
for(int x=num[i];x<num[i]+n+3;x++){
pair <int,int> val=DP::solve(x,x+k);
f[x-num[i]]=val.first;
g[x-num[i]]=val.second;
}
for(int j=1;j<n+3;j++)
f[j]=(f[j]+f[j-1])%mod,g[j]=(g[j]+g[j-1])%mod;
vector <int> y;
for(int j=0;j<n+3;j++)
y.push_back(f[j]);
res1+=Lag(y,num[i+1]-1-num[i]);
res1%=mod;y.clear();
for(int j=0;j<n+3;j++)
y.push_back(g[j]);
res2+=Lag(y,num[i+1]-1-num[i]);
res2%=mod;y.clear();
}
cout<<res1<<"\n"<<res2<<"\n";
return 0;
}
```