题解 P3571 【[POI2014]SUP-Supercomputer】
TIMEONLY
·
·
题解
题意
首先说一下题意,给定一棵N个节点的有根树，根节点为1。Q次询问，每次给定一个K，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过K个未访问的点，且这些点的父亲必须在之前被访问过。
这不是废话吗？题目上写着有!不过说实在话，这题意我开始还真没读懂。
为了简单的表明题意,我就解释一下样例,下面是样例的图
//样例数据
20 1
3
1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11
下面是达到最小操作次数的一种方案（方案按照正确算法模拟而成）
第一次操作:选取1、2、3号节点
第二次操作:选取8、5、4号节点
第三次操作:选取9、7、6号节点(少选了一个，因为没法再选其他节点了)
第四次操作:选取11、10号节点(同样的没法多选)
第五次操作:选取17、18、12号节点(这下能选满了)
第六次操作:选取19、20、13号节点
第七次操作:选取15、14号节点
第八次操作:选取16号节点
完美的在第8次选完!!!
题解
既然题意已经理解了，那么就该说说怎么写出这道题了。
先思考一下,要做到操作次数最小，应该怎么做？
1.每次操作都尽可能的选取更多的节点
2.每次操作都尽可能的选取还有儿子的节点
也就是说每次操作都优先选择还有儿子的节点,如果能选择的有儿子的节点数目小于k,就继续选择没有儿子的节点,直到没有节点可以选或者k次选择用完。
这样贪心的做绝对能够保证答案是正确的。
接下来观察一下数据范围,所有数据都在1e6以内,数据输入也是先输入询问，再输入图，这摆明了需要让我们在O(n)的时间离线预处理,然后O(1)的时间查询。
再看看题目，要求输出最小的操作次数,最小。很有DP的特征，并且DP可以做到预先处理出答案实现O(1)查询。那么就考虑一下DP吧!
定义maxdep表示树上最深的层数
定义s[i]表示深度大于i的节点数量
定义f[i]表示每次最多选i个节点所用的最小操作次数
根据之前的贪心策略可以想到这样的DP方程
f[i]=max(j+⌈s[j]/i⌉);//其中j<=maxdep,注意向上取整
方程的意义如下:
用j次操作选取完前j层,之后的每次操作都能取满i个（或者最后树上剩下不足k个被一次取完）
怎么办?把方程换一种形式来写
```cpp
f[i]=max(⌈(j*i+s[j])/i⌉);//j<=maxdep注意向上取整
```
可以发现,$f_i$的大小已经只和$j*i+s[j]$有关系了，那么我们就可以用斜率优化优化掉一个$O(n)$的转移,时间复杂度变为$O(n)$，可以过掉这道题了
斜率优化就不讲了,要做这题肯定已经会斜率优化了,斜率优化的时候注意一下$f_i$是由区间$[1,maxdep]$转移过来的,和多数斜率优化题$f_i$由区间$[1,i]$转移过来不同,应该先将所有的$j$入队,再进行转移,转移时只需要把已经不是最优的$j$踢出去,不需要再进行入队操作了
------------
## 代码
```cpp
#include<bits/stdc++.h>
#define calc(i,k) i*k+s[i]//斜率优化的一部分
using namespace std;
const int N=1e6+10;
int n,m;
int v[N];
struct EDGE
{
int to,nx;
EDGE(){}
EDGE(int to,int nx):to(to),nx(nx){}
}E[N];
int p;
int head[N];
void build(int a,int b)//建边
{
E[++p]=EDGE(b,head[a]);head[a]=p;
}
int maxdep;//最大深度
int deep[N];//深度为i的节点数目
void chkmax(int &a,int b) {a=a<b?b:a;}
void DFS(int u,int dep)//遍历整棵树,得到树的深度信息,然后就不需要再管这棵树了
{
chkmax(maxdep,dep);deep[dep]++;
for(int i=head[u];i;i=E[i].nx)
DFS(E[i].to,dep+1);
}
int maxk; //最大的询问,f只需要从1转移到maxk就行了
int s[N];//深度大于i的节点数目
int f[N];//每次最多选i次，遍历完整棵树的最少操作次数
//斜率优化用到的变量
int t1,t2;
int q[N];
int a[N],b[N];
inline bool slope(int p1, int p2, int p3)
{
return (b[p3]-b[p1])*(a[p2]-a[p1])-(b[p2]-b[p1])*(a[p3]-a[p1])>=0;
}
int main()
{
//读入,建树
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&v[i]);
chkmax(maxk,v[i]);
}
for(int i=2,x;i<=n;i++)
{
scanf("%d",&x);
build(x,i);
}
//预先处理出s
DFS(1,1);
for(int i=maxdep;i>=1;i--)
s[i]=s[i+1]+deep[i+1];
//提前将j入队
for(int i=1;i<=maxdep;i++) a[i]=i,b[i]=s[i];
//上面代码不能放在下面的循环中,因为下面的循环之前要用到a[i],b[i];
for(int i=1;i<=maxdep;i++)
{
while(t1<t2&&slope(q[t2-1],q[t2],i)) t2--;
q[++t2]=i;
}
//进行转移,不需要再入队,只管踢人
for(int i=1;i<=maxk;i++)
{
while(t1<t2&&calc(q[t1],i)<=calc(q[t1+1],i)) t1++;
f[i]=q[t1]+(s[q[t1]]+i-1)/i;//注意向上取整,不满k个节点还是要用1次操作
}
//输出
for(int i=1;i<=m;i++) printf("%d ",f[v[i]]);
return 0;
}
```