水题笔记_ codevs 1947 道路修建 [树形DP, 手工栈]

srO %%% $Jan$ %%% Orz
jian是我萌的绿太阳!
来跟我一起念: 栈(jian四声)

懵逼的 题目

传送至 Codevs

扯淡的 题解

woc这不是个sb题(flag $\times1$)?
RE
woc数组开大点就A了吧(flag $\times2$)?
MLE
woc栈溢出了?? xjb优化一下就A了吧(flag $\times3$)?
RE
woc还得写手工栈?? 2h后…这肯定能A吧(flag $\times4$)?
没过样例

人生成就达成(1 / 1): flag四连


手工栈啊…实在是太恶心了…自己看着理解吧…
注释挺详细的…

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// codevs1947.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (1000000 + 5)
#define INF (1000000 + 5)
#define LL long long
const int root = 1;
using namespace std;

struct edg
{
int from;
int to;
LL cost;
int next;
};
int n;
LL ans;
edg b[MAXN << 1];
int cntb = 0;
int g[MAXN];
int cur[MAXN];// 当前的节点找到那个子节点了
int f[MAXN];
int fa[MAXN];

inline void adn(int, int, LL);
void dfs(int);
inline LL mabs(LL);
int main()
{
cin >> n;
int srx, sry, srz;
for (int i = 1; i < n; i++)
{
cin >> srx >> sry >> srz;
adn(srx, sry, srz);
adn(sry, srx, srz);
}
fa[root] = 0;
dfs(root);
cout << ans;
return 0;
}
inline void adn(int from, int to, LL cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
cur[from] = g[from] = cntb;
}
inline LL mabs(LL x)
{
return (x > 0) ? (x) : (-x);
}
void dfs(int startDash)
{
bool v[MAXN];// 可有可无?
memset(v, false, sizeof(v));
stack<int> jian;// %%%jian
for (int i = 1; i <= n; i++) f[i] = 1;// 初始化应该放在这里否则gg(或者说我不放在这里就不会写了TUT)
jian.push(startDash);
while (!jian.empty())
{
int dq = jian.top();// 这个地方不能弹栈, 因为还需要回溯
v[dq] = true;
if (!cur[dq])// 注意判定条件: 当前点没有可走的后继了
{
f[fa[dq]] += f[dq];// 更新父节点的 f 值
for (int i = g[dq]; i; i = b[i].next)// 更新 ans
{
if (fa[dq] != b[i].to)
ans += (LL)mabs((n - f[b[i].to]) - f[b[i].to]) * b[i].cost;
}
jian.pop();// 没有后继, 需要回溯的时候再弹栈
continue;
}
for (int i = cur[dq]; i; i = b[i].next)// 从上一次找完的子节点开始找起
{
bool ok = false;// 找到子节点的标志
if (fa[dq] != b[i].to && !v[b[i].to])
{
fa[b[i].to] = dq;
jian.push(b[i].to);
ok = true;
}
cur[dq] = b[i].next;// 不管能不能走, 都要把这条边设为已经找过
if (ok)
{
break;
}
}
}
}
/*
void dfs(int dq)
{
f[dq] = 1;
for (int i = g[dq]; i; i = b[i].next)
{
if (fa[dq] != b[i].to)
{
fa[b[i].to] = dq;
dfs(b[i].to);
f[dq] += f[b[i].to];
}
}
for (int i = g[dq]; i; i = b[i].next)
{
if (fa[dq] != b[i].to)
ans += (LL)mabs((n - f[b[i].to]) - f[b[i].to]) * b[i].cost;
}
}
*/
/*
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
*/

By 被$Jan$碾压着的 Cansult

jan!