結果
| 問題 | No.902 Query ζone |
| ユーザー |
 polylogK
|
| 提出日時 | 2019-09-27 21:03:47 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 21,234 bytes |
| コンパイル時間 | 1,380 ms |
| コンパイル使用メモリ | 88,584 KB |
| 実行使用メモリ | 144,672 KB |
| 最終ジャッジ日時 | 2024-09-24 20:26:47 |
| 合計ジャッジ時間 | 15,173 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | TLE | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
ソースコード
#include <array>
#include <cassert>
using i64 = long long;
struct cluster {
i64 ans;
i64 inter;
i64 sum;
i64 left;
i64 right;
i64 has;
i64 length;
using V = std::size_t;
cluster(i64 l): ans(0), inter(0), sum(0), left(0), right(0), has(0), length(l) {}
static cluster identity() {
return cluster(0);
}
static cluster compress(const cluster& a, const cluster& b, V av, V bv, V cv) {
if(a.has == 0 && b.has == 0) {
if(cv == 0) {
cluster c = identity();
c.ans = (av && bv) * (a.length + b.length);
c.length = a.length + b.length;
return c;
}
else {
cluster c = identity();
c.ans = av * a.length + bv * b.length;
c.left = a.length;
c.right = b.length;
c.has = 1;
c.length = a.length + b.length;
return c;
}
}
else if(a.has == 0) {
if(cv == 0) {
cluster c = identity();
c.inter = b.inter;
c.sum = b.sum;
c.left = a.length + b.left;
c.right = b.right;
c.has = 1;
c.length = a.length + b.length;
c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
return c;
}
else {
cluster c = identity();
c.inter = 0;
c.left = a.length;
c.right = b.right;
c.has = 1;
c.length = a.length + b.length;
c.sum = b.sum + b.left + b.inter;
c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
return c;
}
}
else if(b.has == 0) {
if(cv == 0) {
cluster c = identity();
c.inter = a.inter;
c.sum = a.sum;
c.left = a.left;
c.right = a.right + b.length;
c.has = 1;
c.length = a.length + b.length;
c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
return c;
}
else {
cluster c = identity();
c.inter = 0;
c.left = a.left;
c.right = b.length;
c.has = 1;
c.length = a.length + b.length;
c.sum = a.sum + a.right + a.inter;
c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
return c;
}
}
else {
cluster c = identity();
c.inter = 0;
c.left = a.left;
c.right = b.right;
c.has = 1;
c.length = a.length + b.length;
c.sum = a.sum + b.sum + a.right + b.left + a.inter + b.inter;
c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
return c;
}
}
static cluster rake(const cluster& a, const cluster& b, V av, V bv, V cv) {
if(a.has == 0 && b.has == 0) {
if(bv == 0) {
cluster c = identity();
c.length = a.length;
return c;
}
else {
cluster c = identity();
c.inter = b.length;
c.left = a.length;
c.right = 0;
c.has = 1;
c.length = a.length;
return c;
}
}
else if(a.has == 0) {
if(bv == 0) {
cluster c = identity();
c.inter = b.inter + b.right;
c.sum = b.sum;
c.left = a.length;
c.right = 0;
c.has = 1;
c.length = a.length;
return c;
}
else {
cluster c = identity();
c.inter = b.inter + b.right;
c.sum = b.sum + b.left;
c.left = a.length;
c.right = 0;
c.has = 1;
c.length = a.length;
return c;
}
}
else if(b.has == 0) {
if(bv == 0) {
cluster c = identity();
c.inter = a.inter;
c.sum = a.sum;
c.left = a.left;
c.right = a.right;
c.has = 1;
c.length = a.length;
return c;
}
else {
cluster c = identity();
c.inter = 0;
c.sum = a.sum + a.inter + a.right + b.length;
c.left = a.left;
c.right = 0;
c.has = 1;
c.length = a.length;
return c;
}
}
else {
cluster c = identity();
c.inter = 0;
c.left = a.left;
c.right = 0;
c.has = 1;
c.length = a.length;
c.sum = a.sum + b.sum + a.right + b.right + a.inter + b.inter + bv * b.left;
return c;
}
}
static cluster reverse(const cluster& c) {
cluster res = c;
std::swap(res.left, res.right);
return res;
}
static std::size_t select(const cluster& a, const cluster& b, V av, V bv, V cv) {
return 0;
}
};
class vertex;
class node;
int parent_dir(node*);
node* link(vertex, vertex, cluster);
void test_comp_set(node* n);
class vertex_raw {
cluster::V val;
node* hand;
public:
vertex_raw(cluster::V val): val(val), hand(nullptr) {}
node* handle() const { return this->hand; }
void set_handle(node* hand) { this->hand = hand; }
const cluster::V& value() const { return this->val; }
void set_value(cluster::V val) {
this->val = val;
}
};
class vertex {
vertex_raw* ver;
private:
public:
static vertex dangling() { return vertex(); }
vertex(): ver(nullptr) {}
vertex(cluster::V val): ver( new vertex_raw(val)) {
vertex dummy;
dummy.ver = new vertex_raw(cluster::V());
link(*this, dummy, cluster::identity());
}
bool operator==(const vertex& other) { return this->ver == other.ver; }
inline node* handle() const { return this->ver->handle(); }
inline void set_handle(node* hand) { this->ver->set_handle(hand); }
inline const cluster::V& value() const { return this->ver->value(); }
inline void set_value(cluster::V val) { this->ver->set_value(val); }
};
enum class Type { Compress, Rake, Edge, None };
static std::size_t ni = 0;
extern node ns[1010101];
class node {
node* ch[2];
node* par;
node* ra;
node* me;
bool rev;
cluster fo;
vertex v[2];
Type ty;
public:
node(): par(nullptr), ra(nullptr), me(nullptr), rev(false),
fo(cluster::identity()), ty(Type::None) {}
static node* new_edge(vertex v, vertex u, cluster val) {
//node* n = new node();
node* n = ns + (ni++);
n->v[0] = v;
n->v[1] = u;
n->fo = val;
n->me = n;
n->ty = Type::Edge;
n->fix();
return n;
}
static node* new_compress(node* left, node* right) {
//node* n = new node();
node* n = ns + (ni++);
n->ch[0] = left;
n->ch[1] = right;
n->me = n;
n->ty = Type::Compress;
n->fix();
return n;
}
static node* new_rake(node* left, node* right) {
//node * n = new node();
node* n = ns + (ni++);
n->ch[0] = left;
n->ch[1] = right;
n->me = n;
n->ty = Type::Rake;
n->fix();
return n;
}
inline void fix() {
if(this->ty == Type::Edge) {
if(!this->parent()) {
this->endpoint(0).set_handle(this->me);
this->endpoint(1).set_handle(this->me);
}
else if(this->parent()->ty == Type::Compress) {
if(parent_dir(this->me) == -1) {
this->endpoint(0).set_handle(this->me);
}
}
else if(this->parent()->ty == Type::Rake) {
this->endpoint(0).set_handle(this->me);
}
}
else if(this->ty == Type::Compress) {
this->push();
this->v[0] = this->child(0)->endpoint(0);
this->v[1] = this->child(1)->endpoint(1);
assert(this->child(0)->endpoint(1) == this->child(1)->endpoint(0));
cluster left = this->child(0)->fold();
node* l = this->child(0);
if(this->rake()) {
node* r = this->rake();
left = cluster::rake(l->fold(), r->fold(), l->endpoint(0).value(), r->endpoint(0).value(), l->endpoint(1).value());
}
node* r = this->child(1);
this->fo= cluster::compress(left, r->fold(),
l->endpoint(0).value(), r->endpoint(1).value(), l->endpoint(1).value());
this->child(0)->endpoint(1).set_handle(this->me);
if(!this->parent()) {
this->endpoint(0).set_handle(this->me);
this->endpoint(1).set_handle(this->me);
}
else if(this->parent()->ty == Type::Compress) {
if(parent_dir(this->me) == -1) {
this->endpoint(0).set_handle(this->me);
}
}
else if(this->parent()->ty == Type::Rake) {
this->endpoint(0).set_handle(this->me);
}
}
else if(this->ty == Type::Rake) {
this->push();
this->v[0] = this->child(0)->endpoint(0);
this->v[1] = this->child(0)->endpoint(1);
this->fo = cluster::rake(this->child(0)->fold(), this->child(1)->fold(),
this->child(0)->endpoint(0).value(), this->child(1)->endpoint(0).value(), this->child(0)->endpoint(1).value());
}
else { assert(false); }
}
inline void push() {
if(this->ty == Type::Compress) {
if(this->rev) {
std::swap(this->ch[0], this->ch[1]);
this->child(0)->reverse();
this->child(1)->reverse();
this->rev = false;
}
}
}
inline void reverse() {
if(this->ty == Type::Edge) {
std::swap(this->v[0], this->v[1]);
this->fo = cluster::reverse(this->fold());
}
else if(this->ty == Type::Compress) {
std::swap(this->v[0], this->v[1]);
this->fo = cluster::reverse(this->fold());
this->rev ^= true;
}
else if(this->ty == Type::Rake) {
}
else { assert(false); }
}
inline node* parent() const { return this->par; }
inline void set_parent(node* par) { this->par = par; }
inline node* rake() const { return this->ra; }
inline void set_rake(node* rake) { this->ra = rake; }
inline node* child(std::size_t dir) const { return this->ch[dir]; }
inline void set_child(node* ch, std::size_t dir) { this->ch[dir] = ch; }
inline vertex endpoint(std::size_t dir) { return this->v[dir]; }
inline Type type() const { return this->ty; }
cluster fold() const { return this->fo; }
bool guard;
};
int parent_dir(node* child) {
node* par = child->parent();
if(par) {
if(par->guard) { return -1; }
else if(par->child(0) == child) { return 0; }
else if(par->child(1) == child) { return 1; }
else { return -1; }
}
else { return -1; }
}
int parent_dir_guard(node* child) {
node* par = child->parent();
if(par) {
if(par->child(0) == child) { return 0; }
else if(par->child(1) == child) { return 1; }
else { return -1; }
}
else { return -1; }
}
void rotate(node* t, node* x, std::size_t dir) {
node* y = x->parent();
int par = parent_dir_guard(x);
t->child(dir)->push();
x->set_child(t->child(dir), dir ^ 1);
t->child(dir)->set_parent(x);
t->set_child(x, dir);
x->set_parent(t);
t->set_parent(y);
if(par != -1) {
y->set_child(t, par);
}
else if(y && y->type() == Type::Compress) {
y->set_rake(t);
}
x->fix();
t->fix();
if(y && !y->guard) { y->fix(); }
}
void splay(node* t) {
assert(t->type() != Type::Edge);
t->push();
while(parent_dir(t) != -1) {
node* q = t->parent();
if(q->type() != t->type()) break;
if(parent_dir(q) != -1 && q->parent() && q->parent()->type() == q->type()) {
node* r = q->parent();
if(r->parent()) r->parent()->push();
r->push();
q->push();
t->push();
int qt_dir = parent_dir(t);
int rq_dir = parent_dir(q);
if(rq_dir == qt_dir) {
rotate(q, r, rq_dir ^ 1);
rotate(t, q, qt_dir ^ 1);
}
else {
rotate(t, q, qt_dir ^ 1);
rotate(t, r, rq_dir ^ 1);
}
}
else {
if(q->parent()) q->parent()->push();
q->push();
t->push();
int qt_dir = parent_dir(t);
rotate(t, q, qt_dir ^ 1);
}
}
}
node* expose_raw(node* t) {
while(true) {
assert(t->type() != Type::Rake);
if(t->type() == Type::Compress) {
splay(t);
}
node* n = nullptr;
{
node* par = t->parent();
if(!par) { break; }
else if(par->type() == Type::Rake) {
par->push();
splay(par);
n = par->parent();
}
else if(par->type() == Type::Compress) {
par->push();
if(par->guard && parent_dir_guard(t) != -1) { break; }
n = par;
}
else { assert(false); }
}
splay(n);
int dir = parent_dir_guard(n);
if(dir == -1 || n->parent()->type() == Type::Rake) dir = 0;
if(dir == 1) {
n->child(dir)->reverse();
n->child(dir)->push();
t->reverse();
t->push();
}
int n_dir = parent_dir(t);
if(n_dir != -1) {
node* nch = n->child(dir);
nch->push();
node* rake = t->parent();
rake->push();
rake->set_child(nch, n_dir);
nch->set_parent(rake);
n->set_child(t, dir);
t->set_parent(n);
nch->fix();
rake->fix();
t->fix();
n->fix();
splay(rake);
}
else {
node* nch = n->child(dir);
nch->push();
n->set_rake(nch);
nch->set_parent(n);
n->set_child(t, dir);
t->set_parent(n);
nch->fix();
t->fix();
n->fix();
}
if(t->type() == Type::Edge) {
t = n;
}
}
return t;
}
node* expose(vertex ver) {
return expose_raw(ver.handle());
}
void soft_expose(vertex v, vertex u) {
node* root = expose(v);
if(v.handle() == u.handle()) {
if(root->endpoint(1) == v || root->endpoint(0) == u) {
root->reverse();
root->push();
}
return;
}
root->guard = true;
node* soot = expose(u);
root->guard = false;
root->fix();
if(parent_dir(soot) == 0) {
root->reverse();
root->push();
}
}
node* link(vertex v, vertex u, cluster weight) {
if(!v.handle() && !u.handle()) {
return node::new_edge(v, u, weight);
}
else {
node* nnu = u.handle();
node* nnv = v.handle();
node* e = node::new_edge(v, u, weight);
node* left = nullptr;
if(!nnu) { left = e; }
else {
node* uu = expose_raw(nnu);
uu->push();
if(uu->endpoint(1) == u) {
uu->reverse();
uu->push();
}
if(uu->endpoint(0) == u) {
node* nu = node::new_compress(e, uu);
e->set_parent(nu);
e->fix();
uu->set_parent(nu);
uu->fix();
nu->fix();
left = nu;
}
else {
node* nu = uu;
node* left_ch = nu->child(0);
left_ch->push();
nu->set_child(e, 0);
e->set_parent(nu);
e->fix();
node* beta = nu->rake();
node* rake = nullptr;
if(beta) {
beta->push();
rake = node::new_rake(beta, left_ch);
beta->set_parent(rake);
left_ch->set_parent(rake);
beta->fix();
left_ch->fix();
}
else {
rake = left_ch;
}
nu->set_rake(rake);
rake->set_parent(nu);
rake->fix();
nu->fix();
left = nu;
}
}
if(!nnv) {}
else {
node* vv =expose_raw(nnv);
vv->push();
if(vv->endpoint(0) == v) {
vv->reverse();
vv->push();
}
if(vv->endpoint(1) == v) {
node* top = node::new_compress(vv, left);
vv->set_parent(top);
left->set_parent(top);
vv->fix();
left->fix();
top->fix();
}
else {
node* nv = vv;
node* right_ch = nv->child(1);
right_ch->reverse();
right_ch->push();
nv->set_child(left, 1);
left->set_parent(nv);
left->fix();
node* alpha = nv->rake();
node* rake = nullptr;
if(alpha) {
alpha->push();
rake = node::new_rake(alpha, right_ch);
alpha->set_parent(rake);
alpha->fix();
right_ch->set_parent(rake);
right_ch->fix();
}
else {
rake = right_ch;
}
nv->set_rake(rake);
rake->set_parent(nv);
rake->fix();
nv->fix();
}
}
return e;
}
}
void bring(node* root) {
node* rake = root->rake();
if(!rake) {
node* left = root->child(0);
//delete root, root = nullptr;
left->set_parent(nullptr);
left->fix();
}
else if(rake->type() == Type::Compress || rake->type() == Type::Edge) {
rake->push();
node* new_right = rake;
new_right->reverse();
new_right->push();
root->set_child(new_right, 1);
new_right->set_parent(root);
root->set_rake(nullptr);
new_right->fix();
root->fix();
}
else if(rake->type() == Type::Rake) {
rake->push();
while(rake->child(1)->type() == Type::Rake) {
rake->child(1)->push();
rake = rake->child(1);
}
root->guard = true;
splay(rake);
root->guard = false;
node* new_rake = rake->child(0);
node* new_right = rake->child(1);
//delete rake, rake = nullptr;
new_right->reverse();
new_right->push();
root->set_child(new_right, 1);
new_right->set_parent(root);
root->set_rake(new_rake);
new_rake->set_parent(root);
new_rake->fix();
new_right->fix();
root->fix();
}
}
void cut(vertex v, vertex u) {
soft_expose(v, u);
node* root = v.handle();
root->push();
node* right = root->child(1);
right->set_parent(nullptr);
right->reverse();
right->push();
bring(right);
bring(root);
}
cluster path_query(vertex v, vertex u) {
soft_expose(v, u);
node* root = v.handle();
root->push();
if(root->endpoint(0) == v && root->endpoint(1) == u) {
return root->fold();
}
else if(root->endpoint(0) == v) {
return root->child(0)->fold();
}
else if(root->endpoint(1) == u) {
return root->child(1)->fold();
}
else {
root->child(1)->push();
return root->child(1)->child(0)->fold();
}
}
node* select_rake(node* rake, cluster& right, cluster::V& rv0, cluster::V& rv1) {
rake->push();
while(rake->type() == Type::Rake) {
node* l = rake->child(0);
node* r = rake->child(1);
l->push();
r->push();
cluster rf = cluster::rake(r->fold(), right, r->endpoint(0).value(), rv0, r->endpoint(1).value());
cluster::V r0 = r->endpoint(0).value();
std::size_t dir = cluster::select(l->fold(), rf, l->endpoint(0).value(), r0, l->endpoint(1).value());
r = rake->child(1 - dir);
rake = rake->child(dir);
right = cluster::rake(r->fold(), right, r->endpoint(0).value(), rv0, r->endpoint(1).value());
rv0 = r->endpoint(0).value();
rv1 = r->endpoint(1).value();
rake->push();
}
return rake;
}
std::pair<vertex, vertex> select(vertex v) {
node* n = expose(v);
cluster lf = cluster::identity();
cluster::V l0, l1;
bool luse = false;
cluster rf = cluster::identity();
cluster::V r0, r1;
bool ruse = false;
n->push();
while(n->type() == Type::Compress) {
node* a = n->child(0);
node* b = n->child(1);
node* r = n->rake();
a->push();
b->push();
if(r) { r->push(); }
cluster af = a->fold();
cluster::V a0 = a->endpoint(0).value();
cluster::V a1 = a->endpoint(1).value();
if(luse) {
af = cluster::compress(lf, af, l0, a1, l1);
a0 = l0;
a1 = a1;
}
cluster bf = b->fold();
cluster::V b0 = b->endpoint(0).value();
cluster::V b1 = b->endpoint(1).value();
if(ruse) {
bf = cluster::compress(bf, rf, b0, r1, b1);
b0 = b0;
b1 = r1;
}
cluster arf = af;
if(r) {
arf = cluster::rake(af, r->fold(), a0, r->endpoint(0).value(), a1);
}
std::size_t dir = cluster::select(arf, bf, a0, b1, a1);
if(dir == 0) {
if(r) {
cluster rbf = cluster::reverse(bf);
cluster::V rb0 = b1;
cluster rrf = cluster::rake(r->fold(), rbf, r->endpoint(0).value(), rb0, r->endpoint(1).value());
cluster::V rr0 = r->endpoint(0).value();
cluster::V rr1 = r->endpoint(1).value();
dir = cluster::select(af, rrf, a0, rr0, a1);
if(dir == 0) {
rf = cluster::reverse(rrf);
r0 = rr1;
r1 = rr0;
ruse = true;
n = n->child(0);
}
else {
luse = false;
rf = cluster::rake(af, rbf, a0, rb0, a1);
r0 = a0;
r1 = a1;
ruse = true;
n = select_rake(r, rf, r0, r1);
rf = cluster::reverse(rf);
std::swap(r0, r1);
}
}
else {
rf = bf;
r0 = b0;
r1 = b1;
ruse = true;
n = n->child(0);
}
}
else {
lf = arf;
l0 = a0;
l1 = a1;
luse = true;
n = n->child(1);
}
n->push();
}
return { n->endpoint(0), n->endpoint(1) };
}
node ns[1010101];
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
int main() {
i64 N;
scanf("%lld", &N);
vector<vertex> vs;
for(int i = 0;i < N;i++) {
vs.push_back(vertex(0));
}
for(int i = 0;i < N - 1;i++) {
i64 a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
link(vs[a], vs[b], cluster(c));
}
i64 Q;
scanf("%lld", &Q);
for(i64 q = 0; q < Q; q++) {
i64 k;
scanf("%lld", &k);
vector<i64> vec(k);
for(int i = 0;i < k;i++) scanf("%lld", &vec[i]);
i64 ans = 0;
for(auto a: vec) {
auto node = expose(vs[a]);
vs[a].set_value(1);
node->fix();
ans = node->fold().ans;
}
printf("%lld\n", ans);
for(auto a: vec) {
auto node = expose(vs[a]);
vs[a].set_value(0);
node->fix();
}
}
}