QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222645 | #7608. Cliques | ucup-team956# | WA | 6ms | 26332kb | C++20 | 4.3kb | 2023-10-21 17:54:27 | 2023-10-21 17:54:27 |
Judging History
answer
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
#define int long long
const int _ = 4e5+6;
const int mod=1e9+7;
int n,m,inv2;
vector<int> g[_];
int siz[_],f[_],dep[_],son[_];
int top[_],idx[_],cnt,dsr[_];
int ksm(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=a*ans%mod;
a=a*a%mod;
b>>=1;
} return ans;
}
namespace LCA {
int dep[_],st[_][21];
void dfs(int u,int f) {
for(auto v:g[u]) {
if(v==f) continue;
dep[v]=dep[u]+1;
st[v][0]=u;
dfs(v,u);
}
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;--i)
if(dep[ st[x][i] ]>=dep[y])
x=st[x][i];
if(x==y) return x;
for(int i=20;i>=0;--i)
if(st[x][i]!=st[y][i])
x=st[x][i],y=st[y][i];
return st[x][0];
}
void init() {
dep[1]=1;
dfs(1,0);
FOR(j,1,20) FOR(i,1,n)
st[i][j]=st[st[i][j-1]][j-1];
}
}
namespace seg {
#define ls rt<<1
#define rs rt<<1|1
struct node {
int tot,cnt1,cnt2,lazy;
}e[_<<2];
void pushup(int rt) {
e[rt].tot=(e[ls].tot+e[rs].tot)%mod;
e[rt].cnt1=(e[ls].cnt1+e[rs].cnt1)%mod;
}
void build(int l,int r,int rt) {
e[rt].lazy=1;
e[rt].cnt1=1;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
}
void tag(int rt,int mul) {
e[rt].tot=e[rt].tot*mul%mod;
e[rt].cnt1=e[rt].cnt1*mul%mod;
e[rt].lazy=e[rt].lazy*mul%mod;
}
void pushdown(int rt) {
if(e[rt].lazy!=1) {
tag(ls,e[rt].lazy);
tag(rs,e[rt].lazy);
e[rt].lazy=1;
}
}
void modify_base(int l,int r,int pos,int val,int rt) {
if(l==r) {
e[rt].cnt2=((e[rt].cnt2+1)*val%mod+mod-1)%mod;
e[rt].tot=e[rt].cnt1*e[rt].cnt2%mod;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(pos<=mid) modify_base(l,mid,pos,val,ls);
else modify_base(mid+1,r,pos,val,rs);
pushup(rt);
}
void modify(int l,int r,int L,int R,int mul,int rt) {
if(L<=l&&r<=R) return tag(rt,mul);
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid) modify(l,mid,L,R,mul,ls);
if(R>mid) modify(mid+1,r,L,R,mul,rs);
pushup(rt);
}
array<int,2> query(int l,int r,int L,int rt) {
if(l==r) return {e[rt].cnt1,e[rt].cnt2};
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid) return query(l,mid,L,ls);
else return query(mid+1,r,L,rs);
}
}
void dfs1(int u,int fa) {
dep[u]=dep[fa]+1;
siz[u]=1;
f[u]=fa;
for(auto v:g[u]) {
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int topf) {
top[u]=topf;
dsr[++cnt]=u;
idx[u]=cnt;
if(!son[u]) return;
dfs2(son[u],topf);
for(auto v:g[u]) {
if(!top[v]) dfs2(v,v);
}
}
void MM(int x,int y,int mul) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
seg::modify(1,n,idx[top[x]],idx[x],mul,1);
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
seg::modify(1,n,idx[x],idx[y],mul,1);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
inv2=ksm(2,mod-2);
cin>>n;
FOR(i,2,n) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0),dfs2(1,1);
seg::build(1,n,1);
LCA::init();
cin>>m;
while(m--) {
char c;
int u,v;
cin>>c>>u>>v;
int lca=LCA::lca(u,v);
if(c=='+') {
MM(u,v,2);
MM(lca,lca,inv2);
// if(u!=v) {
// u=f[u],v=f[v];
seg::modify_base(1,n,lca,2,1);
// }
} else {
MM(u,v,inv2);
MM(lca,lca,2);
// if(u!=v) {
// u=f[u],v=f[v];
seg::modify_base(1,n,lca,inv2,1);
// }
}
cout<<seg::e[1].tot<<"\n";
// FOR(i,1,n) {
// auto [x,y]=seg::query(1,n,i,1);
// cout<<x<<" "<<y<<"\n";
// }
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 25508kb
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: 6ms
memory: 26332kb
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 4 2 1 3 7 15 7 15 16 32 65 97 105 97 129 257 261 329 169 137 265 281 145 147 163 151 199 111
result:
wrong answer 2nd lines differ - expected: '3', found: '2'