QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723951#7608. CliquesinksamuraiTL 1ms3556kbC++233.8kb2024-11-08 04:28:392024-11-08 04:28:39

Judging History

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

  • [2024-11-08 04:28:39]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3556kb
  • [2024-11-08 04:28:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

struct treelca{
	int n;
	vi seg;
	vec(vi) adj;
	int timer;
	vi tin,tout,tour,tourid,depth;
	treelca(int m,int root,vec(vi) neadj){
		init(m,root,neadj);
	}
	void init(int m,int root,vec(vi) neadj){
		n=m;
		timer=0;
		tin=tout=tourid=depth=vi(n,0);
		adj=neadj;
		dfs(root,-1);
		seg.resize(4*sz(tour));
		build(1,0,sz(tour)-1);
	}
	void dfs(int v,int par){
		tour.pb(v);
		tourid[v]=sz(tour)-1;
		tin[v]=timer++;
		for(auto u:adj[v]){
			if(u==par) continue;
			depth[u]=depth[v]+1;
			dfs(u,v);
			tour.pb(v);
		}
		tout[v]=timer++;
	}
	void build(int node,int l,int r){
		if(l==r){
			seg[node]=tour[l];
		}else{
			int m=(l+r)>>1;
			build(node*2,l,m);
			build(node*2+1,m+1,r);
			seg[node]=(tin[seg[node*2]]<tin[seg[node*2+1]]?
				seg[node*2]:
				seg[node*2+1]);
		}
	}
	int query(int node,int l,int r,int _l,int _r){
		if(l>_r or r<_l) return -1;
		if(l>=_l and r<=_r) return seg[node];
		int m=(l+r)>>1;
		int vl=query(node*2,l,m,_l,_r),vr=query(node*2+1,m+1,r,_l,_r);
		if(min(vl,vr)==-1) return max(vl,vr);
		return (tin[vl]<tin[vr]?vl:vr);
	}
	int ancestor(int from,int to){
		int tinfrom=tin[from],tinto=tin[to];
		if(tinfrom>tinto) swap(tinfrom,tinto);
		return query(1,0,sz(tour)-1,tinfrom,tinto);
	}
	int dist(int u,int v){
		return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
	}
};

// snuke's mod int
template <ll mod>
struct modint{
	ll x;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

using mint=modint<1000000007>;

typedef vec(mint) vm;

void slv(){
	int n;
	cin>>n;

	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v),adj[v].pb(u);
	}

	vi par(n),dep(n);
	auto dfs=[&](auto self,int v)->void{
		for(auto u:adj[v]){
			if(u==par[v]) continue;
			par[u]=v;
			dep[u]=dep[v]+1;
			self(self,u);
		}
	};
	dfs(dfs,0);

	treelca lca(n,0,adj);

	vi a(n),b(n);
	auto get=[&](int x,int up)->mint{
		mint res=0;
		while(x!=up){
			res+=mint(2).pow(a[x]);
			res-=mint(2).pow(b[x]);
			x=par[x];
		}
		return res;
	};

	auto update=[&](int x,int up,int ad){
		while(x!=up){
			a[x]+=ad;
			b[x]+=ad;
			x=par[x];
		}
	};

	int q;
	cin>>q;
	mint now=0;
	rep(i,q){
		char ch;
		cin>>ch;
		int x,y;
		cin>>x>>y;
		x-=1,y-=1;
		int up=lca.ancestor(x,y);
		if(ch=='+'){
			mint val=get(x,up)+get(y,up);
			val+=mint(2).pow(a[up]);
			now+=val;
			update(x,up,1);
			update(y,up,1);
			a[up]+=1;
		}else{
			update(x,up,-1);
			update(y,up,-1);
			a[up]-=1;
			mint val=get(x,up)+get(y,up);
			val+=mint(2).pow(a[up]);
			now-=val;
		}
		print(now.x);
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t;
	// cin>>t;
	t=1;
	rep(cs,t){
		slv();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3556kb

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: 0
Accepted
time: 0ms
memory: 3544kb

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 
3 
7 
3 
1 
3 
7 
15 
7 
15 
31 
63 
127 
255 
257 
255 
259 
515 
1027 
1283 
643 
385 
769 
1537 
769 
785 
865 
481 
737 
369 

result:

ok 30 lines

Test #3:

score: -100
Time Limit Exceeded

input:

131072
3641 72511
10338 18718
8949 15478
79108 62887
42154 28540
65359 102645
93744 48493
3277 103211
43542 61315
93315 118634
24021 57937
31034 436
30411 6208
1388 25159
93424 128520
119820 87281
5860 97559
59648 8225
57244 58766
119685 13716
130165 60958
79806 116338
97486 80167
101963 95499
51263...

output:

1 
2 
4 
8 
13 
27 
43 
67 
119 
215 
359 
423 
847 
1167 
1935 
2447 
2975 
4511 
5023 
8639 
6911 
13759 
12991 
15103 
23295 
43775 
47999 
91647 
85375 
167295 
169343 
301695 
600703 
666239 
1332351 
2664575 
2678911 
2687103 
5374207 
5898495 
11731455 
11731967 
22283263 
22807551 
21955327 ...

result: