QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#298215 | #7608. Cliques | golikovnik | WA | 1ms | 3528kb | C++20 | 14.0kb | 2024-01-05 20:28:31 | 2024-01-05 20:28:33 |
Judging History
answer
// Nikita Golikov, 2023
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#ifdef GOLIKOV
#include "/Users/golikovnik/contests/debug.h"
#else
#define debug(...) ;
#endif
template <class A, class B>
bool smin(A& x, B&& y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template <class A, class B>
bool smax(A& x, B&& y) {
if (x < y) {
x = y;
return true;
}
return false;
}
// by https://codeforces.com/profile/Nyaan
// example submission:
// https://codeforces.com/contest/1603/submission/133688639
template <uint32_t mod>
struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(r * mod == 1, "invalid, r * mod != 1");
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
u32 a;
constexpr LazyMontgomeryModInt() : a(0) {}
constexpr LazyMontgomeryModInt(const int64_t &b)
: a(reduce(u64(b % mod + mod) * n2)){};
static constexpr u32 reduce(const u64 &b) {
return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
}
constexpr mint &operator+=(const mint &b) {
if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator++() {
return *this += 1;
}
constexpr mint operator++(int) {
auto ret = *this;
*this += 1;
return ret;
}
constexpr mint &operator-=(const mint &b) {
if (i32(a -= b.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator--() {
return *this -= 1;
}
constexpr mint operator--(int) {
auto ret = *this;
*this -= 1;
return ret;
}
constexpr mint &operator*=(const mint &b) {
a = reduce(u64(a) * b.a);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inv();
return *this;
}
constexpr friend mint operator+(mint a, const mint &b) { return a += b; }
constexpr friend mint operator-(mint a, const mint &b) { return a -= b; }
constexpr friend mint operator*(mint a, const mint &b) { return a *= b; }
constexpr friend mint operator/(mint a, const mint &b) { return a /= b; }
constexpr friend bool operator==(mint const& a, const mint &b) {
return (a.a >= mod ? a.a - mod : a.a) == (b.a >= mod ? b.a - mod : b.a);
}
constexpr friend bool operator!=(mint const& a, const mint &b) {
return (a.a >= mod ? a.a - mod : a.a) != (b.a >= mod ? b.a - mod : b.a);
}
constexpr friend bool operator<(mint const& a, const mint &b) {
return (a.a >= mod ? a.a - mod : a.a) < (b.a >= mod ? b.a - mod : b.a);
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint power(int64_t n) const {
mint ret(1), mul(*this);
if (n < 0) {
n = -n;
mul = mul.inv();
}
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
constexpr mint inv() const { return power(mod - 2); }
friend ostream &operator<<(ostream &os, const mint &b) {
return os << b.get();
}
friend istream &operator>>(istream &is, mint &b) {
int64_t t;
is >> t;
b = LazyMontgomeryModInt<mod>(t);
return (is);
}
constexpr u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
constexpr explicit operator int() const {
return int(get());
}
constexpr explicit operator bool() const {
return bool(get());
}
static constexpr u32 get_mod() { return mod; }
};
template <typename T>
struct Binomial {
vector<T> f, g, h;
Binomial(int MAX = 0) : f(1, T(1)), g(1, T(1)), h(1, T(1)) {
extend(MAX + 1);
}
void extend(int m) {
int n = f.size();
if (n >= m) {
return;
}
f.resize(m);
g.resize(m);
h.resize(m);
for (int i = n; i < m; i++) f[i] = f[i - 1] * T(i);
g[m - 1] = f[m - 1].inv();
h[m - 1] = g[m - 1] * f[m - 2];
for (int i = m - 2; i >= n; i--) {
g[i] = g[i + 1] * T(i + 1);
h[i] = g[i] * f[i - 1];
}
}
void extend() {
extend(2 * f.size());
}
T fact(int i) {
if (i < 0) return T(0);
while (i >= (int)f.size()) extend();
return f[i];
}
T ifact(int i) {
if (i < 0) return T(0);
while (i >= (int)g.size()) extend();
return g[i];
}
T inv(int i) {
if (i < 0) return -inv(-i);
while (i >= (int)h.size()) extend();
return h[i];
}
T C(int n, int r) {
if (n < 0 || n < r || r < 0) return T(0);
return fact(n) * ifact(n - r) * ifact(r);
}
inline T operator()(int n, int r) { return C(n, r); }
template <typename I>
T multinomial(const vector<I>& r) {
static_assert(is_integral<I>::value == true);
int n = 0;
for (auto& x : r) {
if(x < 0) return T(0);
n += x;
}
T res = fact(n);
for (auto& x : r) res *= ifact(x);
return res;
}
template <typename I>
T operator()(const vector<I>& r) {
return multinomial(r);
}
T C_naive(int n, int r) {
if (n < 0 || n < r || r < 0) return T(0);
T ret = T(1);
r = min(r, n - r);
for (int i = 1; i <= r; ++i) ret *= inv(i) * (n--);
return ret;
}
T A(int n, int r) {
if (n < 0 || n < r || r < 0) return T(0);
return fact(n) * ifact(n - r);
}
T CR(int n, int r) {
if (n < 0 || r < 0) return T(0);
return r == 0 ? 1 : C(n + r - 1, r);
}
};
// int const MOD = 998244353;
int const MOD = int(1e9 + 7);
using mint = LazyMontgomeryModInt<MOD>;
Binomial<mint> C;
vector<mint> mkpow(mint base, int mx) {
vector<mint> res(mx + 1);
res[0] = 1;
for (int i = 1; i <= mx; ++i) {
res[i] = res[i - 1] * base;
}
return res;
}
template <class T, class M>
struct LazySegmentTree {
int pw;
int n;
int H;
struct Node {
T val{};
M mod{};
void apply(M const& x) {
mod.apply(x);
val.apply(x);
}
Node operator+(Node const& other) const {
return Node{val + other.val};
}
};
vector<Node> tree;
template <class F>
LazySegmentTree(int n_, F const& f) : n(n_), H(0) {
pw = 1;
while (pw < n) {
pw *= 2;
H++;
}
tree.resize(2 * pw);
for (int i = 0; i < n; ++i) {
tree[pw + i].val = f(i);
}
for (int i = pw - 1; i > 0; --i) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
void push(int v) {
tree[2 * v].apply(tree[v].mod);
tree[2 * v + 1].apply(tree[v].mod);
tree[v].mod = M();
}
T query(int ql, int qr) {
ql += pw;
qr += pw;
for (int i = H; i >= 1; --i) {
push(ql >> i);
push((qr - 1) >> i);
}
T L{}, R{};
for (; ql < qr; ql /= 2, qr /= 2) {
if (ql & 1) {
L = L + tree[ql++];
}
if (qr & 1) {
R = tree[--qr] + R;
}
}
return L + R;
}
void modRange(int ql, int qr, M const& mod) {
ql += pw;
qr += pw;
for (int i = H; i >= 1; --i) {
push(ql >> i);
push((qr - 1) >> i);
}
int iql = ql;
int iqr = qr;
for (; ql < qr; ql /= 2, qr /= 2) {
if (ql & 1) {
tree[ql++].apply(mod);
}
if (qr & 1) {
tree[--qr].apply(mod);
}
}
for (int i = 1; i <= H; ++i) {
tree[ql >> i] = tree[ql >> (i - 1)] + tree[ql >> (i - 1) | 1];
tree[(qr - 1) >> i] = tree[(qr - 1) >> (i - 1)] + tree[(qr - 1) >> (i - 1) | 1];
}
}
template <class F>
void modPoint(int at, F const& f) {
at += pw;
for (int i = H; i >= 1; --i) {
push(at >> i);
}
for (f(tree[at].val); at /= 2; ) {
tree[at] = tree[2 * at] + tree[2 * at + 1];
}
}
void setPoint(int at, T const& t) {
modPoint(at, [&](T& x) { x = t; });
}
struct FindResult {
T val{};
int pos = -1;
};
template <class F>
FindResult findFirst(int v, int l, int r, int ql, int qr, F const& f, T pref) {
if (ql >= r || l >= qr) {
return {pref, -1};
}
if (ql <= l && r <= qr) {
if (!f(pref + tree[v].val)) {
return {pref + tree[v].val, -1};
}
if (l + 1 == r) {
return {pref + tree[v].val, l};
}
int m = (l + r) / 2;
push(v);
if (f(pref + tree[2 * v].val)) {
return findFirst(2 * v, l, m, ql, qr, f, pref);
} else {
return findFirst(2 * v + 1, m, r, ql, qr, f, pref + tree[2 * v].val);
}
} else {
int m = (l + r) / 2;
push(v);
auto res = findFirst(2 * v, l, m, ql, qr, f, pref);
if (res.pos == -1) {
return findFirst(2 * v + 1, m, r, ql, qr, f, res.val);
} else {
return res;
}
}
}
template <class F>
FindResult findFirst(int ql, int qr, F const& f) {
return findFirst(1, 0, pw, ql, qr, f, T());
}
template <class F>
FindResult findLast(int v, int l, int r, int ql, int qr, F const& f, T suff) {
if (ql >= r || l >= qr) {
return {suff, -1};
}
if (ql <= l && r <= qr) {
if (!f(tree[v].val + suff)) {
return {tree[v].val + suff, -1};
}
if (l + 1 == r) {
return {tree[v].val + suff, l};
}
int m = (l + r) / 2;
push(v);
if (f(tree[2 * v + 1].val + suff)) {
return findLast(2 * v + 1, m, r, ql, qr, f, suff);
} else {
return findLast(2 * v, l, m, ql, qr, f, tree[2 * v + 1].val + suff);
}
} else {
int m = (l + r) / 2;
push(v);
auto res = findLast(2 * v + 1, m, r, ql, qr, f, suff);
if (res.pos == -1) {
return findLast(2 * v, l, m, ql, qr, f, res.val);
} else {
return res;
}
}
}
template <class F>
FindResult findLast(int ql, int qr, F const& f) {
return findLast(1, 0, pw, ql, qr, f, T());
}
T all() {
return tree[1].val;
}
};
struct HLD {
int n;
vector<int> tin, tout, nxt, depth, par, invtin, sz;
HLD(vector<vector<int>>& g) {
n = int(g.size());
tin.resize(n);
tout.resize(n);
nxt.resize(n);
depth.resize(n);
par.resize(n, -1);
invtin.resize(n);
sz.resize(n);
auto dfs1 = [&](auto self, int v, int p = -1) -> void {
{
auto it = find(g[v].begin(), g[v].end(), p);
if (it != g[v].end()) {
g[v].erase(it);
}
}
sz[v] = 1;
for (int& u : g[v]) {
depth[u] = depth[v] + 1;
par[u] = v;
self(self, u, v);
sz[v] += sz[u];
if (sz[u] > sz[g[v][0]]) {
swap(u, g[v][0]);
}
}
};
int timer = 0;
auto dfs2 = [&](auto self, int v) -> void {
tin[v] = timer++;
invtin[tin[v]] = v;
for (int u : g[v]) {
nxt[u] = (u == g[v][0] ? nxt[v] : u);
self(self, u);
}
tout[v] = timer;
};
dfs1(dfs1, 0);
dfs2(dfs2, 0);
}
template <class F>
void forSubtree(int v, F const& f, bool include = 1) {
f(tin[v] + 1 - include, tout[v]);
}
int LCA(int u, int v) {
while (true) {
int nu = nxt[u];
int nv = nxt[v];
if (nu == nv) {
return depth[u] < depth[v] ? u : v;
}
if (depth[nu] > depth[nv]) {
swap(u, v);
swap(nu, nv);
}
v = par[nv];
}
}
// order is not guaranteed
template <class F>
void forPath(int u, int v, F const& f, bool include = 1) {
while (true) {
int nu = nxt[u];
int nv = nxt[v];
if (nu == nv) {
if (depth[u] < depth[v]) {
f(tin[u] + 1 - include, tin[v] + 1);
} else {
f(tin[v] + 1 - include, tin[u] + 1);
}
return;
}
if (depth[nu] > depth[nv]) {
swap(u, v);
swap(nu, nv);
}
f(tin[nv], tin[v] + 1);
v = par[nv];
}
}
};
int main() {
#ifdef GOLIKOV
assert(freopen("in", "rt", stdin));
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<vector<int>> graph(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
graph[u].push_back(v);
graph[v].push_back(u);
}
HLD hld(graph);
struct M {
mint mul1 = 1;
mint mul2 = 1;
void apply(M const& d) {
mul1 *= d.mul1;
mul2 *= d.mul2;
}
};
struct T {
mint sum1{};
mint sum2{};
T operator+(T const& other) const {
return T{sum1 + other.sum1, sum2 + other.sum2};
}
void apply(M const& d) {
sum1 *= d.mul1;
sum2 *= d.mul2;
}
};
LazySegmentTree<T, M> tree(n, [&](int) {
return T{1, 1};
});
auto ModifyPath = [&](int u, int v, mint x, mint y, bool include) {
debug("path", u, v, x, y, include);
hld.forPath(u, v, [&](int l, int r) {
tree.modRange(l, r, M{x, y});
}, include);
};
auto ModifyPoint = [&](int v, mint x, mint y) {
debug("point", v, x, y);
tree.modPoint(hld.tin[v], [&](T& val) {
val.sum1 *= x;
val.sum2 *= y;
});
};
auto Modify = [&](int u, int v, mint mul) {
ModifyPath(u, v, mul, mul, 1);
ModifyPoint(hld.LCA(u, v), 1, 1 / mul);
};
int q; cin >> q;
while (q--) {
char ch;
int u, v;
cin >> ch >> u >> v;
--u, --v;
Modify(u, v, ch == '+' ? 2 : C.inv(2));
cout << tree.all().sum1 - tree.all().sum2 << '\n';
}
#ifdef GOLIKOV
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
5 1 2 5 1 2 3 4 2 6 + 4 5 + 2 2 + 1 3 - 2 2 + 2 3 + 4 4
output:
1 3 7 3 7 9
result:
ok 6 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3460kb
input:
20 8 7 19 10 12 14 3 16 17 13 7 10 5 6 1 9 15 12 5 2 16 13 3 11 20 14 18 6 1 14 16 20 11 10 3 4 20 6 30 + 10 20 + 14 20 + 12 17 - 14 20 - 12 17 + 4 6 + 8 20 + 3 6 - 10 20 + 2 17 + 1 16 + 6 10 + 9 10 + 5 15 + 7 8 - 7 8 + 2 5 + 3 18 + 1 20 + 8 16 - 3 18 - 5 15 + 4 20 + 14 16 - 4 6 + 8 19 + 4 7 - 1 16 ...
output:
1 2 5 3 1 3 7 15 7 15 31 63 127 131 133 131 135 519 527 1287 647 639 771 1539 775 787 867 483 495 423
result:
wrong answer 2nd lines differ - expected: '3', found: '2'