香港记者跑的比谁都快是众所周知的常识。
现在，香港记者站在一颗有 n 个点的树的根结点上(即1号点)，编号为 i 的点拥有权值 a[i] ，数据保证每个点的编号都小于它任意孩子结点的别号。
我们假定这棵树的每个叶子结点都在发生一个大新闻，香港记者要用最少的耗时去报道其中的任意一个。
若香港记者目前处于第 i 号点上，那么它可以移动至以 i 为根的子树上的任意一点 j ，耗时 a[i]+(j−i)p ，p为给定常数。
请问这位香港记者搞哪个大新闻的耗时最短？所耗时间是多少？
解题报告:
用时:3h,2WA4TLE
这题开始写没写出来，然后想着优化\(O(n^2)\)的暴力，于是开了个以\(val[x]+f[x]\)为判断条件的单调栈，然后还是TLE65
最后写的决策单调性:
对于一个点x，存在一个管辖的范围，在这个范围内x的转移是最优的，然后我们就维护这个东西，每次新加入一个点，我们拿这个点和栈顶的点分别和管辖的那个点计算然后作比较，维护单调性，然后每一次转移，我们二分到第一个能管辖到x的点就是最优转移，求一个点能管辖的范围，那么就二分一个\((x'-x)^p\)中的\(x'\),直到它刚好比栈顶元素优为止，其后就是它能管辖的范围
还有对于树上的栈维护，还要消除子树间的影响，我们进入一颗子树前，还要把在其他子树弹出的元素都放回栈中.
复杂度\(O(nlogn)\)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e5+5;
typedef long long ll;
const ll inf=1e18;
int head[N],to[N<<1],n,nxt[N<<1],num=0,val[N],p;
void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
ll ans=inf,f[N],mul[N];
ll qm(ll x,ll k){
ll sum=1;
while(k){
if(k&1)sum*=x;
x*=x;k>>=1;
}
return sum;
}
bool vis[N];
struct node{
int x,last,fo;
node(){}
node(int _x,int _last,int _fo){x=_x;last=_last;fo=_fo;}
}q[N],st[N];
int top=0,stop=0,du[N];
void dfs(int x,int last){
int u;
if(x!=1){
int l=1,r=top,mid,ret=l,last;
while(l<=r){
mid=(l+r)>>1;
if(q[mid].last<=x)ret=mid,l=mid+1;
else r=mid-1;
}
f[x]=f[q[ret].x]+val[q[ret].x]+mul[x-q[ret].x];
while(top && q[top].last>=x){
u=q[top].x;last=q[top].last;
if(f[x]+val[x]+mul[last-x]<=f[u]+val[u]+mul[last-u])
st[++stop]=q[top--],st[stop].fo=x;
else break;
}
l=Max(q[top].last+1,x+1);r=n;ret=0;u=q[top].x;
while(l<=r){
mid=(l+r)>>1;
if(f[x]+val[x]+mul[mid-x]<=f[u]+val[u]+mul[mid-u])
ret=mid,r=mid-1;
else l=mid+1;
}
if(ret)q[++top]=node(x,ret,0);
}
else f[x]=0,q[++top]=node(1,1,0);
if(!du[x])ans=Min(ans,f[x]);
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last)continue;
dfs(u,x);
}
if(q[top].x==x)top--;
while(stop && st[stop].fo==x)q[++top]=st[stop--];
}
void work()
{
int x;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++){
scanf("%d%d",&val[i],&x);
if(x)link(x,i),link(i,x),du[x]++;
}
for(int i=0;i<=n;i++){
mul[i]=qm(i,p);
if(mul[i]>=inf){
for(int j=i;j<=n;j++)
mul[j]=inf;
break;
}
}
dfs(1,1);
printf("%lld\n",ans);
}
int main()
{
work();
return 0;
}