結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-09-04 02:26:20 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 285 ms / 3,000 ms |
コード長 | 5,854 bytes |
コンパイル時間 | 2,393 ms |
コンパイル使用メモリ | 174,084 KB |
実行使用メモリ | 34,420 KB |
最終ジャッジ日時 | 2024-12-25 21:27:21 |
合計ジャッジ時間 | 5,459 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#define M_PI 3.14159265358979323846using namespace std;//conversion//------------------------------------------inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }inline int readInt() { int x; scanf("%d", &x); return x; }//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<int, PII> TIII;typedef long long LL;typedef unsigned long long ULL;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//container util//------------------------------------------#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define SQ(a) ((a)*(a))#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)#define EXIST(s,e) ((s).find(e)!=(s).end())#define SORT(c) sort((c).begin(),(c).end())//repetition//------------------------------------------#define FOR(i,s,n) for(int i=s;i<(int)n;++i)#define REP(i,n) FOR(i,0,n)#define MOD 1000000007#define rep(i, a, b) for(int i = a; i < (b); ++i)#define trav(a, x) for(auto& a : x)#define all(x) x.begin(), x.end()#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;const double EPS = 1E-8;#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)const int INF = 100000000;struct Edge {int to, from;ll cost;Edge(int from, int to, ll cost): from(from), to(to), cost(cost) {}};struct UnionFind {vector<int> data;UnionFind(int size) : data(size, -1) { }bool unionSet(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;}return x != y;}bool findSet(int x, int y) {return root(x) == root(y);}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}};typedef vector<vector<Edge>> AdjList;AdjList graph;bool comp(const Edge& e1, const Edge& e2) {return e1.cost < e2.cost;}vector<int> split_naive(const string &s, char delim) {vector<int> elems;string item;for (char ch: s) {if (ch == delim) {if (!item.empty())elems.push_back(atoi(item.c_str()));item.clear();}else {item += ch;}}if (!item.empty())elems.push_back(atoi(item.c_str()));return elems;}ll mod_pow(ll x, ll n, ll mod){ll res = 1;bool c = false;while(n){if(n&1) res = res * x;if(res > mod){c = true;res %= mod;}x = x * x %mod;n >>= 1;}if(c) return mod;return res;}#define SIEVE_SIZE 9000*9000bool sieve[SIEVE_SIZE];void make_sieve(){for(int i=0; i<SIEVE_SIZE; ++i) sieve[i] = true;sieve[0] = sieve[1] = false;for(int i=2; i*i<SIEVE_SIZE; ++i) if(sieve[i]) for(int j=2; i*j<SIEVE_SIZE; ++j) sieve[i*j] = false;}bool isprime(ll n){for(ll i=2; i*i<=n; ++i) if(n%i==0) return false;return true;}template<typename T>vector<T> gauss_jordan(const vector<vector<T>>& A, const vector<T>& b){int n = A.size();vector<vector<T>> B(n, vector<T>(n+1));for(int i=0; i<n; ++i){for(int j=0; j<n; ++j){B[i][j] = A[i][j];}}for(int i=0; i<n; ++i) B[i][n] = b[i];for(int i=0; i<n; ++i){int pivot = i;for(int j=i; j<n; ++j){if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j;}swap(B[i], B[pivot]);if(abs(B[i][i]) < EPS) return vector<T>(); //解なしfor(int j=i+1; j<=n; ++j) B[i][j] /= B[i][i];for(int j=0; j<n; ++j){if(i != j){for(int k=i+1; k<=n; ++k) B[j][k] -= B[i][j] * B[i][k];}}}vector<T> x(n);for(int i=0; i<n; ++i) x[i] = B[i][n];return x;}typedef complex<double> P;namespace std {bool operator < (const P& a, const P& b) {return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);}}double cross(const P& a, const P& b) {return imag(conj(a)*b);}double dot(const P& a, const P& b) {return real(conj(a)*b);}struct L : public vector<P> {L(const P &a, const P &b) {push_back(a); push_back(b);}};struct C {P p; double r;C(const P &p, double r) : p(p), r(r) { }};int ccw(P a, P b, P c) {b -= a; c -= a;if (cross(b, c) > 0) return +1; // counter clockwiseif (cross(b, c) < 0) return -1; // clockwiseif (dot(b, c) < 0) return +2; // c--a--b on lineif (norm(b) < norm(c)) return -2; // a--b--c on linereturn 0;}ll GCD(ll a, ll b){if(b == 0) return a;return GCD(b, a%b);}ll ans = 0;ll N;vector<vector<pair<int, ll>>> G(200010);vector<ll> scale;void dfs(int curr, int prev, ll d){for(int i=0; i<G[curr].size(); ++i){int next = G[curr][i].first;if(next != prev) dfs(next, curr, G[curr][i].second);}if(prev == -1) return;scale[prev] += scale[curr];ans += d*scale[curr]*(N-scale[curr]) * 2;}int main() {//cin.tie(0);//ios::sync_with_stdio(false);//cout << fixed << setprecision(10);cin >> N;scale.resize(N,1);for(int i=0; i<N-1; ++i){int u, v, w; cin >> u >> v >> w;u--; v--;G[u].push_back({v, w});G[v].push_back({u, w});}dfs(0, -1, -1);cout << ans << endl;return 0;}