题目大意
我们称一个有根树的节点u是 k-ary heap of depth m 的，当且仅当其满足以下条件之一：
1. m=1
2. m>1，u有至少k个儿子是至少 k-ary heap of depth m-1的（即儿子可以是 k-ary heap of depth n的，n≥m）
给定一个n个节点的有根树（1是树根）。设dp[k][u]表示一个最大的m，满足u为根的子树中存在节点是 k-ary heap of depth m 的。
求： ∑nk=1∑nu=1dp[k][u]
n≤300,000
分析
设h[k][u]表示一个最大的m，满足u是 k-ary heap of depth m 的。
暴力显然是枚举k，然后dfs这棵树，做完u的所有儿子后，把儿子的h值拿出来，用nth_element找到第k大值并赋h[k][u]为其加1。最后dfs一遍求出dp[k][]
对于k=1，我们这样O(n)地做，对于k>1，我们发现如下性质：
1.h[k][u]≤lognk
2.h[k][u]≥h[k+1][u]
我们考虑设f[u][j]表示一个最大的k，满足h[k][u]=j。这个状态数显然是 O(nlogn) 的
那么我们预处理这个f数组可以递归并根据定义计算，做完u的儿子后，枚举j，把所有f[v][j-1]（v是u的儿子）拿出来降序排序，找到最大的k，满足第k大的f大于等于k。那么这个k即是f[u][j]。这个过程是 O(nlog2n) 的，但是常数小且一般跑不满
得到了f数组后，我们可以降序枚举k，把所有f[u][j]=k的无序对(u,j)拿出来，用j去往根跑更新dp数组。根据前面的性质1，更新的次数是nlogn的，所以这个部分的时间复杂度是 O(nlogn)
#include using namespace std;
const int N=3e5+5,M=20;
typedef long long LL;
LL ans,sum;
int n,h[N],e[N<<1],nxt[N<<1],tot,f[N][M],g[N],D[N],Dep[N],p,q,fa[N],a[N];
bool vis[N];
typedef pair PII;
vector 【[codeforces955F] Heaps】 H[N];
void Add(int x,int y)
{
e[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}void dfs(int x)
{
f[x][1]=n;
g[x]=1;
for (int i=h[x];
i;
i=nxt[i]) if (e[i]!=fa[x])
{
fa[e[i]]=x;
dfs(e[i]);
g[x]=max(g[x],g[e[i]]+1);
}
ans+=g[x];
for (int j=2;
j0) a[++cnt]=f[e[i]][j-1];
if (cnt==0) break;
sort(a+1,a+cnt+1);
for (i=cnt;
i>0 && cnt-i+1<=a[i];
i--);
if (i==0 || cnt-i+1>a[i]) i++;
f[x][j]=cnt-i+1;
H[f[x][j]].push_back(make_pair(x,j));
}
}int main()
{
scanf("%d",&n);
for (int i=1,x,y;
i1;
k--)
{
vector ::iterator it;
for (it=H[k].begin();
it!=H[k].end();
it++)
{
PII tmp=*it;
for (int i=tmp.first;
i && g[i] 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）