跑的比谁都快 51Nod

香港记者跑的比谁都快是众所周知的常识。

现在，香港记者站在一颗有

n

我们假定这棵树的每个叶子结点都在发生一个大新闻，香港记者要用最少的耗时去报道其中的任意一个。

若香港记者目前处于第

i

请问这位香港记者搞哪个大新闻的耗时最短？所耗时间是多少？

Input第一行两个数n<=100000、p<=10，代表树上点的个数以及题中所提及的常数p。
接下来n行，第i行有两个数字a $i$ Output每组数据输出一行为最短耗时。Sample Input

Sample Output

849


先谢谢Jessie Liu大佬的点拨。
题解：
　　这个题目，我们先考虑一条链的情况，设dp[i]表示i这个节点到1节点的最小花费，那么dp[i]=dp[j]+cost[j~i]，这个是十分显然的，所以在链上枚举i的每个前驱节点就可以。 
　　换成一棵树，因为一棵树是由很多条链来组成的，对于节点i，我们可以枚举每个祖先来j来dp，状态转移是一样的，但是具体怎么在树上枚举祖先呢？可以开一个栈记录一下所经过的深度的节点就看了。
　　因为是指数函数，可以看出有决策单调性，那么就记一下父节点是从哪里转移的，从那里开始枚举就可以了。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 100100
#define ll long long
using namespace std;
struct edge{
    int first;
    int next;
    int to;
}a[MAXN*2];
ll dp[MAXN],node[MAXN],fa[MAXN],stk[MAXN],last[MAXN],ans=1ll<<60;
int n,p,num=0;

void addedge(int from,int to){
    a[++num].to=to;
    a[num].next=a[from].first;
    a[from].first=num;
}

ll pw(ll base,int h){
    ll ans=1;
    while(h){
        if(h&1) ans=ans*base;
        base*=base;h>>=1;
    }
    return ans;
}

void dfs(int now,int dep){
    stk[dep]=now;
    for(int j=last[fa[now]];j<dep;j++){
        ll cnt=dp[stk[j]]+node[stk[j]]+pw(now-stk[j],p);
        if(dp[now]>cnt) dp[now]=cnt,last[now]=j;
    }
    int sz=0;
    for(int i=a[now].first;i;i=a[i].next){
        int to=a[i].to;
        if(to==fa[now]) continue;
        sz++;
        dfs(to,dep+1);
    }
    if(!sz) ans=min(ans,dp[now]);
}

int main()
{
    scanf("%d%d",&n,&p);
    memset(dp,37,sizeof(dp));
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&node[i],&fa[i]);
        addedge(i,fa[i]),addedge(fa[i],i);
    }
    dp[1]=0;
    dfs(1,0);
    printf("%lld",ans);
    return 0;
}