树形DP+决策单调性
考虑优化DP。
构一条链的数据，打表，发现决策点单调，因此套决策单调性即可O(nlogn)。
知识漏洞，以前对决策单调性的理解一直存在误区。决策单调性是指对于 i < j，那么一定有i的决策点<=j的决策点，但并不保证决策函数是单峰的。因此不能直接从上一个决策点开始枚举，遇到不优就停下来。正确做法是主动转移，然后二分。详见《1D/1D 动态规划优化初步》里面的第一部分。
在树上的话，记录退栈就可以了。
话说这题好像数据很水，卡不掉错误算法？
#include<cstdio>#include<queue>#define N 100005#define cmin(u,v) ((u)>(v)?(u)=(v):0)using namespace std;namespace runzhe2000{typedef long long ll;const ll INF = 1000000000000000000ll;int n, ecnt, p, a[N], last[N], stacnt, licnt;ll ans, f[N], pow[N];struct edge{int next, to;}e[N<<1];void addedge(int a, int b){e[++ecnt] = (edge){last[a], b};last[a] = ecnt;}struct stack{int u, p, from;}sta[N], list[N];void dfs(int x){if(x == 1) f[x] = 0;else{int l = 1, r = stacnt;for(; l < r; ){int mid = (l+r+1)>>1;if(sta[mid].p <= x) l = mid;else r = mid - 1;}int u = sta[l].u;f[x] = f[u] + a[u] + pow[x - u];}if(x == 1) sta[++stacnt] = (stack){x, 2, 0};else{int u, p;for(;;){u = sta[stacnt].u, p = sta[stacnt].p;if(x < p && f[x] + a[x] + pow[p-x] < f[u] + a[u] + pow[p-u]) list[++licnt] = sta[stacnt--], list[licnt].from = x;else break;}int l = max(x+1, p+1), r = n+1; for(; l < r; ){int mid = (l+r)>>1;if(f[x] + a[x] + pow[mid-x] < f[u] + a[u] + pow[mid-u]) r = mid;else l = mid + 1;}if(l <= n) sta[++stacnt] = (stack){x, l, 0};}bool end = 1; for(int i = last[x]; i; i = e[i].next){dfs(e[i].to);end=0;}if(end) cmin(ans, f[x]);if(sta[stacnt].u == x) --stacnt;for(; licnt && list[licnt].from == x; )sta[++stacnt] = list[licnt--];}void main(){scanf("%d%d",&n,&p);for(int i = 1, x; i <= n; i++){scanf("%d%d",&a[i],&x);x ? addedge(x, i),0 : 0;}for(int i = 1; i <= n; i++){ll tmp = 1; bool fuck = 0;for(int j = 1; j <= p; j++) (tmp * i) < tmp ? fuck = 1 : tmp *= i;pow[i] = fuck ? INF : tmp;}ans = INF; dfs(1);printf("%lld\n",ans);}} int main(){runzhe2000::main();}
