QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222645#7608. Cliquesucup-team956#WA 6ms26332kbC++204.3kb2023-10-21 17:54:272023-10-21 17:54:27

Judging History

你现在查看的是最新测评结果

  • [2023-10-21 17:54:27]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:26332kb
  • [2023-10-21 17:54:27]
  • 提交

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'