結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-01 23:28:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 5,080 bytes |
コンパイル時間 | 2,086 ms |
コンパイル使用メモリ | 179,568 KB |
実行使用メモリ | 21,304 KB |
最終ジャッジ日時 | 2024-10-12 19:07:35 |
合計ジャッジ時間 | 3,653 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:172:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 172 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:176:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 176 | scanf("%d %d", &A, &B); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:186:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 186 | scanf("%d", &U[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:188:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 188 | scanf("%d", &M); | ~~~~~^~~~~~~~~~ main.cpp:192:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 192 | scanf("%d %d %d", &A, &B, &C); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;vector< vector< int > > graph;struct BinaryIndexedTree{vector< int > data;BinaryIndexedTree(int sz){data.assign(++sz, 0);}int sum(int k){int ret = 0;for(++k; k > 0; k -= k & -k) ret += data[k];return(ret);}void add(int k, int x){for(++k; k < data.size(); k += k & -k) data[k] += x;}};struct CentroidPathDecomposition{struct Centroid{int ParIndex, ParDepth, Deep;vector< int > node;inline int size(){return(node.size());}inline int &operator[](int k){return(node[k]);}inline pair< int, int > Up(){return(make_pair(ParIndex, ParDepth));}};vector< int > SubTreeSize, NextPath;vector< int > TreeIndex, TreeDepth;vector< Centroid > Centroids;void BuildSubTreeSize(){stack< pair< int, int > > s;s.push({0, -1});while(!s.empty()) {auto p = s.top(); s.pop();if(~SubTreeSize[p.first]) {NextPath[p.first] = -1;for(auto& to : graph[p.first]) {if(p.second == to) continue;SubTreeSize[p.first] += SubTreeSize[to];if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) {NextPath[p.first] = to;}}} else {s.push(p);SubTreeSize[p.first] = 1;for(auto& to : graph[p.first]) {if(p.second != to) s.push({to, p.first});}}}}void BuildPath(){stack< pair< int, int > > s;Centroids.push_back((Centroid){-1, -1, 0});s.push({0, -1});TreeIndex[0] = 0;while(!s.empty()) {auto p = s.top(); s.pop();TreeDepth[p.first] = Centroids[TreeIndex[p.first]].size();for(auto& to : graph[p.first]) {if(p.second != to) {if(to == NextPath[p.first]) { // Centroid-PathTreeIndex[to] = TreeIndex[p.first];} else { // Not Centroid-PathTreeIndex[to] = Centroids.size();Centroids.push_back((Centroid){TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1});}s.push({to, p.first});}}Centroids[TreeIndex[p.first]].node.push_back(p.first);}}void AddEdge(int x, int y){graph[x].push_back(y);graph[y].push_back(x);}void Build(){BuildSubTreeSize();BuildPath();}inline int size(){return(Centroids.size());}inline pair< int, int > Information(int idx){return(make_pair(TreeIndex[idx], TreeDepth[idx]));}inline Centroid &operator[](int k){return(Centroids[k]);}inline int LCA(int a, int b) // これを流用する{int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;tie(TreeIdxA, TreeDepthA) = Information(a);tie(TreeIdxB, TreeDepthB) = Information(b);while(TreeIdxA != TreeIdxB) {if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();} else {tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();}}if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);return(Centroids[TreeIdxA][TreeDepthA]);}CentroidPathDecomposition(int SZ){graph.resize(SZ);SubTreeSize.assign(SZ, -1);NextPath.resize(SZ);TreeIndex.resize(SZ);TreeDepth.resize(SZ);}inline void AddPath(int A, int B, int C, vector< BinaryIndexedTree >& bits);};inline void CentroidPathDecomposition::AddPath(int A, int B, int C, vector< BinaryIndexedTree >& bits){int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;tie(TreeIdxA, TreeDepthA) = Information(A);tie(TreeIdxB, TreeDepthB) = Information(B);while(TreeIdxA != TreeIdxB) {if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {bits[TreeIdxA].add(0, C);bits[TreeIdxA].add(TreeDepthA + 1, -C);tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();} else {bits[TreeIdxB].add(0, C);bits[TreeIdxB].add(TreeDepthB + 1, -C);tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();}}if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);bits[TreeIdxA].add(TreeDepthA, C);bits[TreeIdxA].add(TreeDepthB + 1, -C);}int main(){int N, M, U[100000];scanf("%d", &N);CentroidPathDecomposition tree(N);for(int i = 0; i < N - 1; i++) {int A, B;scanf("%d %d", &A, &B);tree.AddEdge(A, B);}tree.Build();vector< BinaryIndexedTree > bits;for(int i = 0; i < tree.size(); i++) {bits.push_back(BinaryIndexedTree(tree[i].size() + 2));}for(int i = 0; i < N; i++) {scanf("%d", &U[i]);}scanf("%d", &M);while(M--) {int A, B, C;scanf("%d %d %d", &A, &B, &C);tree.AddPath(A, B, C, bits);}long long ret = 0;for(int i = 0; i < N; i++) {int idx, depth;tie(idx, depth) = tree.Information(i);ret += 1LL * bits[idx].sum(depth) * U[i];}printf("%lld\n", ret);}