QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#302488 | #7608. Cliques | defyers# | TL | 3ms | 77336kb | C++20 | 3.9kb | 2024-01-10 22:12:37 | 2024-01-10 22:12:38 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using ll = long long;
using LL = long long;
using pii = pair<int, int>;
const int N = 5e5 + 11;
const int LGN = 20;
int p[N], sz[N], dep[N], dfn[N], id = 0, head[N], anc[LGN][N];
vector<int> G[N], ch[N];
void dfs0(int v, int pa = -1){
if(pa == -1){
p[v] = v; for(int j = 0; j < LGN; j++) anc[j][v] = v;
}
sz[v] = 1;
for(auto u : G[v]){
if(u == pa) continue;
anc[0][u] = p[u] = v;
for(int j = 1; j < LGN; j++)
anc[j][u] = anc[j - 1][anc[j - 1][u]];
dep[u] = dep[v] + 1;
dfs0(u, v); sz[v] += sz[u];
ch[v].push_back(u);
}
sort(ch[v].begin(), ch[v].end(), [](auto x, auto y){
return sz[x] > sz[y];
});
}
void dfs1(int v, int h){
// cout << "DFS1 " << v << ' ' << h << endl;
head[v] = h;
if(ch[v].size()){
int u = ch[v][0];
dfn[u] = ++id;
dfs1(u, v == 0 ? dfn[u] : h);
}
for(int i = 1; i < ch[v].size(); i++){
int u = ch[v][i];
dfn[u] = ++id;
dfs1(u, dfn[u]);
}
}
int kth_anc(int v, int k){
for(int j = LGN - 1; j >= 0; j--){
if((1 << j) & k) v = anc[j][v];
}
return v;
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v); u = kth_anc(u, dep[u] - dep[v]);
for(int j = LGN - 1; j >= 0; j--){
if(anc[j][u] != anc[j][v])
u = anc[j][u], v = anc[j][v];
}
return u == v ? u : p[u];
}
#define int long long
const int MOD = 1e9 + 7;
int mi2 = (MOD + 1) / 2;
int n;
void chmul(int& x, int y){
x = (x * y) % MOD;
}
struct SegTree{
int t[N << 2], lz[N << 2];
void init(int v = 0, int l = 1, int r = n){
lz[v] = 1;
if(l == r) t[v] = 1;
else {
int m = (l + r) / 2;
init(v * 2 + 1, l, m);
init(v * 2 + 2, m + 1, r);
t[v] = (t[v * 2 + 1] + t[v * 2 + 2]) % MOD;
}
}
void push(int v){
if(lz[v] != 1){
chmul(lz[v * 2 + 1], lz[v]);
chmul(lz[v * 2 + 2], lz[v]);
chmul(t[v * 2 + 1], lz[v]);
chmul(t[v * 2 + 2], lz[v]);
lz[v] = 1;
}
}
void update(int ql, int qr, int qv, int v = 0, int l = 1, int r = n){
// if(v == 0) printf("UPDATE %lld %lld %lld\n", ql, qr, qv);
if(qr < l || r < ql || qr < ql) return;
if(ql <= l && r <= qr) t[v] = (t[v] * qv) % MOD, lz[v] = (lz[v] * qv) % MOD;
else {
int m = (l + r) / 2; push(v);
update(ql, qr, qv, v * 2 + 1, l, m);
update(ql, qr, qv, v * 2 + 2, m + 1, r);
t[v] = (t[v * 2 + 1] + t[v * 2 + 2]) % MOD;
}
}
int qry(){
return t[0];
}
};
struct HLD{
SegTree ST;
void init(){
ST.init();
}
void add(int v, int l, int inc){
int mul = inc == 1 ? 2 : mi2;
while(head[v] != head[l]){
ST.update(dfn[head[v]], dfn[v], mul);
v = p[head[v]];
}
ST.update(dfn[l], dfn[v], mul);
}
int qry(){
return ST.qry();
}
} HLD0, HLD1;
void solve(int TC) {
cin >> n;
G[0].push_back(1);
for(int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs0(0); dfs1(0, 0);
// for(int i = 1; i <= n; i++) cout << dfn[i] << ' '; cout << '\n';
// for(int i = 1; i <= n; i++) cout << head[i] << ' '; cout << '\n';
HLD0.init(), HLD1.init();
int q; cin >> q;
for(int i = 0; i < q; i++){
char op; cin >> op; int u, v; cin >> u >> v;
int l = lca(u, v);
#ifdef LOCAL
cout << "LCA: " << l << ' ' << u << ' ' << v << endl;
#endif
int inc = op == '+' ? 1 : -1;
int pu = kth_anc(u, dep[u] - dep[l] - 1);
int pv = kth_anc(v, dep[v] - dep[l] - 1);
if(u != l) HLD0.add(u, pu, inc), HLD1.add(u, pu, inc);
if(v != l) HLD0.add(v, pv, inc), HLD1.add(v, pv, inc);
HLD0.add(l, l, inc);
int a = HLD0.qry();
int b = HLD1.qry();
int ans = ((a - b) % MOD + MOD) % MOD;
cout << ans << '\n';
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 77336kb
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
Time Limit Exceeded
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 ...