虚树
其实就是把原树浓缩成 \(k_i\) 数量级的小树，题目会保证 \(\sum k_i\) 和 \(n\) 同阶，于是每次询问暴力 dp 就是对的了。
但是 OI-Wiki 并未提到为什么 dp 用到的所有点是关键点本身和排完序后每相邻两个关键点的 LCA 呢？
证明
虚树的建立：
il bool cmp(int a,int b){
return id[a]<id[b];
}
il void build(){
t[++num]=1;
sort(a+1,a+k+1,cmp);
for(int i=1;i<k;i++){
t[++num]=a[i];
t[++num]=LCA(a[i],a[i+1]);
} t[++num]=a[k];
sort(t+1,t+num+1,cmp);
num=unique(t+1,t+num+1)-t-1;
for(int i=1;i<num;i++) vec[LCA(t[i],t[i+1])].push_back(t[i+1]);
}
P2495 [SDOI2011] 消耗战
板子题。
考虑暴力：设 \(dp_u\) 表示使 \(u\) 子树内所有关键点都与 \(1\) 断开的最小代价，令 \(Min_u\) 表示 \(1\) 到 \(u\) 的路径上边权最小值。
\[ f_u=\left\{\begin{matrix} Min_u & [u 是关键点]\\ \min(Min_u,\sum f_{to}) & [u 不是关键点] \end{matrix}\right. \]虚树建出来就可以了。
dp 部分代码：
il void dfs(int u){
dp[u]=0;
for(auto to:vec[u]){
dfs(to);
dp[u]+=dp[to];
} if(st[u]) dp[u]=Min[u];
else dp[u]=min(dp[u],1ll*Min[u]);
vec[u].clear(); st[u]=false;
}
P4103 [HEOI2014] 大工程
先考虑最小最大值。
定义 \(Min_u\) 和 \(Max_u\) 表示 \(u\) 子树内所有关键点到 \(u\) 的最小/最大值。
答案有两种情况：
-
\(u\) 是关键点，在儿子中找到最小/最大值。
-
\(u\) 不是关键点，找两个儿子的值拼起来即可。
再考虑代价和，其实就是计算每一条边对答案的贡献。
定义 \(dp_u\) 表示 \(u\) 子树内所有关键点到 \(u\) 的距离和，\(g_u\) 表示 \(u\) 子树内关键点个数。
将 \(u\) 到 \(to\) 这一段路径的长度记为 \(w\)，\(to\) 儿子的贡献即为 \((g_u-g_{to}) \times (dp_{to}+g_{to} \times w)\)，即就是除开 \(to\) 儿子后其他关键点和 \(to\) 子树连边的次数乘上 \(to\) 子树内所有关键点到 \(u\) 的距离和。
建出虚树即可。dp 代码：
il void dfs(int u){
dp[u]=g[u]=0;
Mindep[u]=INF,Maxdep[u]=-INF;
if(st[u]) g[u]=1,Mindep[u]=Maxdep[u]=0;
for(auto to:vec[u]){
dfs(to);
int w=dep[to]-dep[u];
Min=min(Min,Mindep[u]+Mindep[to]+w);
Max=max(Max,Maxdep[u]+Maxdep[to]+w);
Mindep[u]=min(Mindep[u],Mindep[to]+w);
Maxdep[u]=max(Maxdep[u],Maxdep[to]+w);
g[u]+=g[to],dp[u]+=dp[to]+w*g[to];
} for(auto to:vec[u]){
int w=dep[to]-dep[u];
ans+=1ll*(g[u]-g[to])*(dp[to]+w*g[to]);
} st[u]=false,vec[u].clear();
}
CF613D Kingdom and its Cities
先考虑无解的情况：一个点是关键点且他的父亲也是关键点。
建立出虚树后，还是分两种情况讨论：
-
\(u\) 是关键点，则需要将它与儿子节点的路径断掉。
-
\(u\) 不是关键点，记 \(cnt\) 为它的儿子节点中关键点的数量，若 \(cnt>1\)，则将 \(u\) 占领。若 \(cnt=1\)，则将 \(u\) 标记为关键点，回溯到父节点去短边。
dp 代码：
il int dfs(int u){
int res=0,cnt=0;
for(auto to:vec[u]) res+=dfs(to),cnt+=(st[to]?1:0);
if(st[u]) res+=cnt;
else{
if(cnt>1) res++;
else if(cnt==1) st[u]=true;
} return res;
}
咕咕咕。
标签：cnt,Min,int,笔记,学习,Maxdep,虚数,dp,关键点 From： https://www.cnblogs.com/Celestial-cyan/p/18122375