[51nod1789] 跑得比谁都快

题面

题解

设\(f[i]\)为根节点到\(i\)的最小耗时

设\(S\)为\(i\)的祖先集合, 可以得到

\[f[i] = min(f[j] + (i - j)^p),j \in S
\]

对于\((i - j)^p\), 我们有

\[((i + 1) - (j + 1))^p + (i - j)^p \leq ((i + 1) - j)^p + (i - (j + 1))^p
\]

可以发现这是一个满足四边形不等式的式子

直接上决策单调性即可(我这个写法是看的别人的, 应该是对的吧)

Code

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <vector>

#define itn int

#define reaD read

#define N 100005

using namespace std;

int n, p, w[N], cnt;

long long pw[N], ans;

template < typename T >

inline T read()

{

	T x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }

	return x * w;

}

namespace Graph

{

	int head[N];

	struct edge { int to, next; } e[N];

	inline void adde(int u, int v) { e[++cnt] = (edge) { v, head[u] }; head[u] = cnt; }

};

using namespace :: Graph;

long long fpow(long long x, int y = p)

{

	long long res = 1;

	for( ; y; y >>= 1, x = 1ll * x * x)

		if(y & 1) res = 1ll * res * x;

	return res;

}

namespace DFS

{

	long long f[N];

	int top, stk[N], pos[N];

	struct node { int l, r, id; } q[N];

	void dfs(int u, int fa)

	{

		if(u == 1) stk[++top] = u, f[u] = 0, pos[u] = top;

		else

		{

			int num;

			long long tmp = f[0];

			for(int i = pos[fa]; i <= top; i++)

			{

				long long res = f[stk[i]] + w[stk[i]] + fpow(u - stk[i], p);

				if(res <= tmp) num = i, tmp = res;

			}

			f[u] = tmp;

			pos[u] = num;

			stk[++top] = u;

		}

		bool flag = 0;

		for(int i = head[u]; i; i = e[i].next)

			flag = 1, dfs(e[i].to, u);

		if(!flag) ans = min(ans, f[u]);

		top--;

	}

};

using namespace :: DFS;

int main()

{

	n = read <int> (); p = read <int> ();

	for(int i = 1; i <= n; i++)

	{

		w[i] = read <int> (); int u = read <int> ();

		if(u) adde(u, i);

	}

	memset(f, 0x3f, sizeof(f));

	ans = f[0];

	dfs(1, 0);

	printf("%lld\n", ans);

	return 0;

}