結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2020-02-03 23:49:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 755 ms / 2,000 ms |
コード長 | 3,669 bytes |
コンパイル時間 | 2,084 ms |
コンパイル使用メモリ | 203,916 KB |
最終ジャッジ日時 | 2025-01-08 22:00:58 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using PII = std::pair<int, int>;using PLL = std::pair<ll, ll>;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)const int amax = 18;struct node{int depth;vector<ll> custom;vector<ll> ansestors;vector<ll> childrens;vector<ll> roads;};vector<node> nodes;void dfs(ll s, ll d){nodes[s].depth = d;for (auto z : nodes[s].roads){if (nodes[z].depth == -1){dfs(z, d + 1);nodes[s].childrens.push_back(z);}else{nodes[s].ansestors[0] = z;}}}ll cost_to_ansestors(ll s, ll n){ll m, c;c = 0;if (n == 0)return 0;else{m = n;while (m > 0 && m % 2 == 0){c++;m /= 2;}return nodes[s].custom[c] + cost_to_ansestors(nodes[s].ansestors[c], n - pow(2, c));}}ll back_to_ansestors(ll s, ll n){ll m, c;c = 0;if (n == 0)return s;else{m = n;while (m > 0 && m % 2 == 0){c++;m /= 2;}return back_to_ansestors(nodes[s].ansestors[c], n - pow(2, c));}}ll lca(ll a, ll b){ll dd, ok, ng, mid;dd = nodes[a].depth - nodes[b].depth;if (dd > 0)a = back_to_ansestors(a, dd);if (dd < 0)b = back_to_ansestors(b, abs(dd));if (a == b)return a;if (a == 0 || b == 0)return 0;while (nodes[a].ansestors[0] != nodes[b].ansestors[0]){for (int i = amax - 1; i > -1; i--){if (nodes[a].ansestors[i] != nodes[b].ansestors[i]){a = nodes[a].ansestors[i];b = nodes[b].ansestors[i];break;}}}return nodes[a].ansestors[0];}int main(){#ifdef DEBUGcout << "DEBUG MODE" << endl;ifstream in("input.txt"); //for debugcin.rdbuf(in.rdbuf()); //for debug#endifll n, k, q, a, b, c, d, ans;cin >> n;vector<ll> cusint, ainit, cinit, rinit;rep(i, n){nodes.push_back((node){-1, cusint, ainit, cinit, rinit});}rep(i, n - 1){cin >> a >> b;nodes[a].roads.push_back(b);nodes[b].roads.push_back(a);}rep(i, n){rep(j, amax){nodes[i].custom.push_back(0);nodes[i].ansestors.push_back(-1);}cin >> k;nodes[i].custom[0] = k;}dfs(0, 0);rep(j, amax - 1){rep(i, n){if (nodes[i].ansestors[j] != -1 && nodes[nodes[i].ansestors[j]].ansestors[j] != -1){nodes[i].ansestors[j + 1] = nodes[nodes[i].ansestors[j]].ansestors[j];nodes[i].custom[j + 1] = nodes[nodes[i].ansestors[j]].custom[j] + nodes[i].custom[j];}}}ans = 0;cin >> q;rep(i, q){cin >> a >> b >> c;d = lca(a, b);ans += c * nodes[d].custom[0];ans += c * cost_to_ansestors(a, nodes[a].depth - nodes[d].depth);ans += c * cost_to_ansestors(b, nodes[b].depth - nodes[d].depth);}cout << ans << endl;// rep(i, n)// {// cout << nodes[i].depth << "\t";// rep(j, amax)// {// cout << nodes[i].custom[j] << " ";// }// cout << "\t" << cost_to_ansestors(i, nodes[i].depth);// cout << endl;// }return 0;}