結果

問題 No.386 貪欲な領主
ユーザー yosupot
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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
*
* linkcutevertparent, root
*
*/
struct LCNode {
using NP = LCNode*;
static NP last;
ll d;
ll dsm;
NP init_last() {
sz = 0; // Important
d = dsm = 0;
return this;
}
void init_node() {
sz = 1; rev = false; // Important
d = dsm = 0;
}
void update() {
sz = 1 + l->sz + r->sz; // Important
dsm = d + l->dsm + r->dsm;
}
void set(int d) {
this->d = d;
update();
}
void push() {
assert(this != last);
if (rev) { // Important
if (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0