QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222126 | #7608. Cliques | PhantomThreshold# | WA | 3ms | 27984kb | C++20 | 2.4kb | 2023-10-21 15:58:04 | 2023-10-21 15:58:04 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;
const int maxn = 410000;
const int mod = 1e9+7;
const int inv2 = (mod+1)>>1;
int n;
vector<int>E[maxn];
void addedge(int x,int y)
{
E[x].push_back(y);E[y].push_back(x);
}
int siz[maxn],son[maxn],fa[maxn],dep[maxn];
void dfs(const int x)
{
son[x]=0;
siz[x]=1;
for(auto y:E[x]) if(y!=fa[x])
{
dep[y]=dep[x]+1;
fa[y]=x;
dfs(y);
siz[x]+=siz[y];
if( siz[son[x]] < siz[y] ) son[x]=y;
}
}
int top[maxn],dfn[maxn],dfi,idfn[maxn];
void build(const int x,const int tp)
{
dfn[x]=++dfi; idfn[dfi]=x;
top[x]=tp;
if(son[x])
build(son[x],tp);
for(auto y:E[x]) if(y!=fa[x] && y!=son[x])
build(y,y);
}
struct segment
{
int seg[maxn<<2],flag[maxn<<2];
void build(const int x,const int l,const int r)
{
flag[x]=1;
if(l==r)
{
seg[x]= (idfn[l]>n)?mod-1:1;
return;
}
int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
build(lc,l,mid); build(rc,mid+1,r);
seg[x]=(seg[lc]+seg[rc])%mod;
}
void pushdown(const int x)
{
if(flag[x]!=1)
{
int fl=flag[x]; flag[x]=1;
int lc=x<<1,rc=lc|1;
seg[lc]=(ll)seg[lc]*fl%mod;
seg[rc]=(ll)seg[rc]*fl%mod;
flag[lc]=(ll)flag[lc]*fl%mod;
flag[rc]=(ll)flag[rc]*fl%mod;
}
}
int lx,rx,c;
void upd(const int x,const int l,const int r)
{
if(rx<l||r<lx) return;
if(lx<=l&&r<=rx)
{
seg[x]=(ll)seg[x]*c%mod;
flag[x]=(ll)flag[x]*c%mod;
return;
}
pushdown(x);
int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
upd(lc,l,mid); upd(rc,mid+1,r);
seg[x]=(seg[lc]+seg[rc])%mod;
}
int query()
{
return seg[1];
}
}seg;
void UPD(int x,int y,int c)
{
int f1=top[x],f2=top[y];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(x,y);
swap(f1,f2);
}
seg.lx=dfn[f1],seg.rx=dfn[x],seg.c=c;
seg.upd(1,1,dfi);
x=fa[f1],f1=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
seg.lx=dfn[x],seg.rx=dfn[y],seg.c=c;
seg.upd(1,1,dfi);
}
signed main()
{
//freopen("tmp.in","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int x,y; cin>>x>>y;
addedge(x,n+i);
addedge(y,n+i);
}
dep[1]=1; dfs(1);
dfi=0; build(1,1);
seg.build(1,1,dfi);
// cout<<seg.query()-1<<endl;
int Q; cin>>Q;
while(Q--)
{
string str; cin>>str;
int x,y; cin>>x>>y;
if(str[0]=='+') UPD(x,y,2);
else UPD(x,y,inv2);
cout<<(seg.query()-1+mod)<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 27984kb
input:
5 1 2 5 1 2 3 4 2 6 + 4 5 + 2 2 + 1 3 - 2 2 + 2 3 + 4 4
output:
1000000008 1000000010 1000000014 1000000010 1000000014 1000000016
result:
wrong answer 1st lines differ - expected: '1', found: '1000000008'