【反思】为什么这么久？

题目：求一颗带点权的二叉树的中心。

这么水的一道题居然写了这么久。

还是效率问题。

看来....还是要学会休息，学会学习，合理安排时间神马的...连着搞太久也不好。搞完一下午，晚上就没有精神了。

代码还写得这么丑..真是。

Code

#include<iostream>
#include<cstdio> 
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<climits>
#define ot "%d"
#ifdef WIN32
#define otl "%I64d"
#else
#define otl "%lld"
#endif
//#define link(a, b) ({nt[++tot] = h[a]; t[h[a] = tot] = b; nt[++tot] = h[b]; t[h[b] = tot] = a;})
#define min(a, b) ({int _ = (a), __ = (b); _ < __ ? _ : __;})
#define swap(t, a, b) ({t _ = (a); (a) = (b); (b) = _;})
#define maxn 100005

using namespace std;

int n, c[2][maxn], s[maxn], ans, k, v[maxn], num[maxn];

void init()
{
	freopen("hospital.in", "r", stdin);
	freopen("hospital.out", "w", stdout);
	scanf(ot, &n);
	for (int i = 1; i <= n; ++i)
		scanf(ot ot ot, &num[i], &c[0][i], &c[1][i]);
}

void dfs(int k)
{
	if (!k) return ;
	int l = c[0][k], r = c[1][k];
	dfs(l), dfs(r); s[k] = s[l] + s[r];
	v[k] = v[l] + v[r] + s[k]; s[k] += num[k];
}

void update(int k, int chn, int vu)
{
	if (!k) return;
	int l = c[0][k], r = c[1][k], sl = s[l], sr = s[r], vk = v[k] = vu;
	update(l, chn + num[k] + sr, vk - sl + chn + num[k] + sr), update(r, chn + num[k] + sl, vk - sr + chn + num[k] + sl);
}

int main()
{
	init();
	v[0] = c[0][0] = c[1][0] = s[0] = 0;
	dfs(1);
	ans = v[1];
	int l = c[0][1], r = c[1][1], sl = s[l], sr = s[r], vk = v[1];
	update(l, s[r] + num[1], vk - sl + sr + num[1]), update(r, s[l] + num[1], vk - sr + sl + num[1]);
	for (int i = 2; i <= n; ++i) ans = min(ans, v[i]);
	printf(ot, ans);
	return 0;
}

不过..还是要加油~

El psy congroo