#include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr ll TEN(int n) { return (!n) ? 1 : 10 * TEN(n-1); } template using Graph = vector>; /** * 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; // 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; }