/*#include <iostream>
using namespace std;
template<typename T>
ostream& print(ostream& os, const T& t)
{
return os << t;
}
template <typename T, typename... Args>
ostream& print(ostream& os, const T& a, const Args&... rest) {
os << a << '\n';
return print(os, rest...);
}
int main() {
print(cout, 4, 5, 6, 7, 8, 9, 10);
return 0;
}*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5 + 5;
int n, a[maxn], w[maxn];
vector <pair<int, long long>> g[maxn];
int used[maxn];
long long dp1[maxn], ben1[maxn];
long long dp2[maxn], ben2[maxn];
int sz[maxn];
long long answ;
void sizeCounter(int v, int p){
sz[v] = 1;
dp1[v] = dp2[v] = 0;
ben1[v] = ben2[v] = 0;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
if (to == p || used[to]) continue;
sizeCounter(to, v);
sz[v] += sz[to];
}
}
int center = 0;
void findCen(int v, int p){
int cnt = sz[v] / 2 + 1;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
if (to == p || used[to]) continue;
if (sz[to] > cnt){
center = to;
findCen(to, v);
}
}
}
vector <long long> G;
void push_DP(int v, int p){
sz[v] = 1;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
int len = g[v][i].second;
if (to == p || used[to]) continue;
ben1[to] = ben1[v] + a[v] - len;
dp1[to] = dp1[v];
if (ben1[to] < 0){
dp1[to] -= ben1[to];
ben1[to] = 0;
}
int d = a[to] - len;
dp2[to] = dp2[v] + d;
ben2[to] = min(1ll * d, ben2[v] + d);
push_DP(to, v);
sz[v] += sz[to];
}
if (ben2[v] >= 0){
G.push_back(dp2[v]);
}
}
int findCenter(int v){
sizeCounter(v, -1);
center = v;
findCen(v, -1);
push_DP(center, -1);
return center;
}
vector <long long> P;
vector <int> ver;
void solve(int v, int p){
if (p != -1){
ver.push_back(v);
if (ben2[v] >= 0){
P.push_back(dp2[v]);
}
}
int idx = lower_bound(G.begin(), G.end(), dp1[v]) - G.begin();
answ += (int)G.size() - idx;
if (p == -1) answ--;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
if (to == p || used[to]) continue;
solve (to, v);
if (p == -1){
sort (P.begin(), P.end());
for (int j = 0; j < ver.size(); j++){
int u = ver[j];
int id = lower_bound(P.begin(), P.end(), dp1[u]) - P.begin();
answ -= (int)P.size() - id;
}
P.clear();
ver.clear();
}
}
}
void centroidDecomposition() {
queue <int> q;
q.push(1);
while (!q.empty()) {
int v = q.front();
q.pop();
v = findCenter(v);
sort(G.begin(), G.end());
solve(v, -1);
G.clear();
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
if (used[to] || sz[to] == 1) continue;
q.push(to);
}
used[v] = 1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
g[x].push_back({ y, z });
g[y].push_back({ x, z });
}
centroidDecomposition();
cout << answ << '\n';
return 0;
}
Compilation message
transport.cpp: In function 'void sizeCounter(int, int)':
transport.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
transport.cpp: In function 'void findCen(int, int)':
transport.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
transport.cpp: In function 'void push_DP(int, int)':
transport.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
transport.cpp: In function 'void solve(int, int)':
transport.cpp:119:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
transport.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < ver.size(); j++){
~~^~~~~~~~~~~~
transport.cpp: In function 'void centroidDecomposition()':
transport.cpp:147:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
transport.cpp: In function 'int main()':
transport.cpp:163:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
transport.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
transport.cpp:168:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
3068 KB |
Output is correct |
| 2 |
Correct |
10 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
233 ms |
3756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1035 ms |
11228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
14256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
18204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1048 ms |
6112 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
7288 KB |
Output is correct |
| 2 |
Correct |
645 ms |
7064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
9004 KB |
Output is correct |
| 2 |
Correct |
202 ms |
8972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
387 ms |
10848 KB |
Output is correct |
| 2 |
Correct |
335 ms |
10692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
13700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
