51nod 1789 跑的比谁都快

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stack>
#define MAXN 100050
#define INF 2000000000000000000LL
#define LL long long
using namespace std;
int n, p, numEdge, top, root;
bool lef[MAXN];
int head[MAXN], star[MAXN];
LL dp[MAXN], ans;
struct Edge
{
    int v, next;
}edge[MAXN];
void addEdge(int u, int v)
{
    edge[numEdge].v = v;
    edge[numEdge].next = head[u];
    head[u] = numEdge++;
}
struct Node
{
    int id, l, r;
    Node(int I = 0, int L = 0, int R = 0): id(I), l(L), r(R){};
}S[MAXN];
LL quickPow(LL a, LL b)
{
    LL res = 1LL;
    while(b)
    {
        if(b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
LL work(int i, int j)
{
    return quickPow(j - i, p) + (LL)star[i];
}
void dfs(int u)
{
    stack<Node> tmp;
    int tmpR = -1;
    int lft = 1, rit = top, mid;
    if(u == root)
    {
        dp[u] = 0;
        S[++top] = Node(root, 1, n);
    }
    else
    {
        while(lft <= rit)                    //初始化dp[u]
        {
            mid = (lft + rit) >> 1;
            if(S[mid].l <= u && u <= S[mid].r)
            {
                dp[u] = dp[S[mid].id] + work(S[mid].id, u);
                break;
            }
            if(u < S[mid].l) rit = mid - 1;
            else   lft = mid + 1;
        }
        while(top > 0)                        //决策单调性的经典操作
        {
            if(dp[S[top].id] + work(S[top].id, S[top].l) < dp[u] + work(u, S[top].l))
            {
                lft = S[top].l, rit = S[top].r;
                while(lft <= rit)            //二分找出breakpoint
                {
                    mid = (lft + rit) >> 1;
                    if(dp[S[top].id] + work(S[top].id, mid) < dp[u] + work(u, mid))
                        lft = mid + 1;
                    else
                        rit = mid - 1;
                }
                tmpR = S[top].r;
                S[top].r = rit;
                break;
            }
            tmp.push(S[top]);                                //记录下从栈中撤出的元素到tmp中
            top--;
        }
        if(lft <= n) S[++top] = Node(u, lft, n);
    }
    if(head[u] == -1) ans = min(ans, dp[u]);
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        dfs(v);
    }
    if(u != root)
    {
        if(lft <= n) top--;
        if(tmpR != -1) S[top].r = tmpR;
        while(!tmp.empty())                                    //回溯的时候恢复栈
        {
            S[++top] = tmp.top();
            tmp.pop();
        }
    }
}
int main()
{
    scanf("%d%d", &n, &p);
    star[0] = numEdge = top = 0;
    for(int i = 0; i <= n; i++) head[i] = -1, lef[i] = true;
    root = 1;
    for(int fa, i = 1; i <= n; i++)
    {
        scanf("%d%d", &star[i], &fa);
        addEdge(fa, i);
        lef[fa] = false;
    }
    ans = INF;
    dfs(root);
    cout << ans << endl;
    return 0;
}