数组开太大了
by 氷芽川四糸乃 @ 2019-07-31 17:38:15
@[Long_Ping](/space/show?uid=53204) 题解里的数组和我开的一样大啊
by Fraction @ 2019-07-31 18:19:39
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, cnt;
ll ans;
int sizes[100005], head[200010];
int w[100005];
struct Edge {
int to;
int nxt;
} edge[200010];
void addedge(int from, int to, int dis) {
edge[++cnt].to = to;
edge[cnt].nxt = head[from];
w[cnt] = dis;
head[from] = cnt;
}
void dfs(int now, int last) {
sizes[now] = 1;
for(int i = head[now]; i; i = edge[i].nxt) {
int vv = edge[i].to;
if(vv != last) {
dfs(vv, now);
ans += (ll)abs(n - 2*sizes[vv]) * w[i];
sizes[now] += sizes[vv];
}
}
}
void init() {
int u, v, w;
cin >> n;
for(int i = 1; i < n; i++) {
cin >> u >> v >> w;
addedge(u, v, w), addedge(v, u, w);
}
}
void solve() {
dfs(1, 0);
cout << ans;
}
int main() {
init();
solve();
return 0;
}
```
这样就有55分
by D447H @ 2020-02-19 17:18:38