結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-01 22:47:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 562 ms / 2,000 ms |
コード長 | 4,726 bytes |
コンパイル時間 | 660 ms |
コンパイル使用メモリ | 66,416 KB |
実行使用メモリ | 9,596 KB |
最終ジャッジ日時 | 2024-10-12 03:50:33 |
合計ジャッジ時間 | 4,354 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <cstdio>#include <iostream>#include <vector>#include <queue>#include <algorithm>#include <numeric>#include <cassert>using namespace std;using ll = long long;constexpr ll TEN(int n) { return (!n) ? 1 : 10 * TEN(n-1); }template <class E>using Graph = vector<vector<E>>;/*** Link-Cut Tree** 機能としては、link、cut、evert、parent, rootを実装済み* 辺に値を持たせたい場合は頂点倍加*/struct LCNode {using NP = LCNode*;static NP last;ll d;ll dsm;NP init_last() {sz = 0; // Importantd = dsm = 0;return this;}void init_node() {sz = 1; rev = false; // Importantd = dsm = 0;}void update() {sz = 1 + l->sz + r->sz; // Importantdsm = d + l->dsm + r->dsm;}void set(int d) {this->d = d;update();}void push() {assert(this != last);if (rev) { // Importantif (l != last) {l->revdata();}if (r != last) {r->revdata();}rev = false;}}void revdata() {rev ^= true; swap(l, r); // Important}void addch(NP b) {assert(b == last || b->p == this);}void delch(NP b) {assert(b == last || b->p == this);}//ここからNP p, l, r;int sz;bool rev;LCNode() : p(nullptr), l(last), r(last) {}inline int pos() {if (p) {if (p->l == this) return -1;if (p->r == this) return 1;}return 0;}void rot() {NP q = p->p;int pps = p->pos();if (pps == -1) {q->l = this;}if (pps == 1) {q->r = this;}if (p->l == this) {p->l = r;if (r) r->p = p;r = p;} else {p->r = l;if (l) l->p = p;l = p;}p->p = this;p->update();update();p = q;if (q) q->update();}void splay() {supush();int ps;while ((ps = pos())) {int pps = p->pos();if (!pps) {rot();} else if (ps == pps) {p->rot(); rot();} else {rot(); rot();}}}void expose() {for (NP u = this; u; u = u->p) {u->splay();}for (NP u = this, ur = last; u; u = u->p) {NP tmp = u->r;u->r = last;u->update();u->addch(tmp);u->delch(ur);u->r = ur;u->update();ur = u;}splay();}void supush() {if (pos()) {p->supush();}push();}//ここまでは絶対必要void link(NP r) {expose();r->expose();p = r;r->addch(this);}NP parent() {expose();NP u = this->l;if (u == last) return last;u->push();while (u->r != last) {u = u->r;u->push();}u->expose();return u;}void cut() {NP u = parent();assert(u != last);assert(u->r == last);this->splay();u->delch(this);this->p = nullptr;}NP root() {expose();NP u = this;while (u->l != last) {u = u->l;u->push();}u->expose();return u;}void evert() {expose();revdata();}NP lca(NP n) {n->expose();expose();NP t = n;while (n->p != nullptr) {if (!n->pos()) t = n->p;n = n->p;}return (this == n) ? t : nullptr;}};LCNode::NP LCNode::last = (new LCNode())->init_last();const int MN = 100200;LCNode lc[MN];int main() {int n;cin >> n;assert(2 <= n and n <= 100000);for (int i = 0; i < n; i++) {lc[i].init_node();}for (int i = 0; i < n-1; i++) {int a, b;cin >> a >> b;lc[a].evert();lc[a].link(lc+b);}for (int i = 0; i < n; i++) {int u;cin >> u;lc[i].evert();lc[i].set(u);}int m;cin >> m;ll ans = 0;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;assert(a != b);lc[a].evert();lc[b].expose();ans += lc[b].dsm * c;}cout << ans << endl;return 0;}