QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227668#7610. Bus Lines275307894aTL 2075ms60128kbC++144.0kb2023-10-27 20:57:372023-10-27 20:57:38

Judging History

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

  • [2023-10-27 20:57:38]
  • 评测
  • 测评结果:TL
  • 用时:2075ms
  • 内存:60128kb
  • [2023-10-27 20:57:37]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=N*8+5,K=(1<<25)+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,x,y;
vector<int> S[N];
int fa[N],d[N],Sn[N],Si[N],Tp[N],Bg[N],Bh,En[N],Df[N];
void dfs1(int x,int La){
	fa[x]=La;d[x]=d[La]+1;Si[x]=1;
	for(int i:S[x]) if(i^La) dfs1(i,x),Si[x]+=Si[i],Si[Sn[x]]<Si[i]&&(Sn[x]=i);
}
void dfs2(int x,int La){
	Df[Bg[x]=++Bh]=x;Tp[x]=La;if(Sn[x]) dfs2(Sn[x],La);
	for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);En[x]=Bh;
}
vector<pair<int,int> > E;
int LCA(int x,int y){
	E.clear();while(Tp[x]^Tp[y]) {
		if(d[Tp[x]]<d[Tp[y]]) swap(x,y);
		E.emplace_back(Bg[Tp[x]],Bg[x]);x=fa[Tp[x]];
	}
	if(d[x]>d[y]) swap(x,y);E.emplace_back(Bg[x],Bg[y]);return x;
} 
ll f[N],g[N],w[N],ans[N];int up[N];
struct node{int x,y,ti;};
vector<node> Q[N];vector<pair<int,int> > D[N];
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	int g[M],Ct;ll Sum[M],f[M];
	void Up(int v){f[v]=(g[v]?Sum[v]:f[ls]+f[rs]);}
	void PF(int v,int w){g[v]+=w;Up(v);}
	void Add(int x,int y,int w,int l=1,int r=n,int v=1){
		if(x<=l&&r<=y) return PF(v,w);int m=l+r>>1;
		x<=m&&(Add(x,y,w,l,m,ls),0);y>m&&(Add(x,y,w,m+1,r,rs),0);Up(v);
	}
	void modify(int x,ll w,int l=1,int r=n,int v=1){
		Sum[v]+=w;if(l==r) return Up(v);int m=l+r>>1;
		x<=m?modify(x,w,l,m,ls):modify(x,w,m+1,r,rs);Up(v);
	}
	ll qry(int x,int y,int op=0,int l=1,int r=n,int v=1){
		if(x>y) return 0;op|=g[v];
		if(x<=l&&r<=y) return op?Sum[v]:f[v];int m=l+r>>1;
		return (x<=m?qry(x,y,op,l,m,ls):0)+(y>m?qry(x,y,op|g[v],m+1,r,rs):0);
	}
}
int YAI;
int MIN(int x,int y){return d[x]<d[y]?x:y;}
void ins(int x,int La,int w,int ti){
	for(auto i:Q[x]) if(i.ti<ti) Tree::Add(i.x,i.y,w),YAI++;
	for(int i:S[x]) if(i^La) ins(i,x,w,ti);
}
void dfs3(int x,int La){
	for(int i:S[x]) if(i^La&&i^Sn[x]) dfs3(i,x),ins(i,x,-1,d[i]);
	if(Sn[x]) dfs3(Sn[x],x)/*,ins(Sn[x],x,-1)*/;
	for(int i:S[x]) if(i^La&&i^Sn[x]) ins(i,x,1,d[i]);
	for(auto i:Q[x]) Tree::Add(i.x,i.y,1);
	for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
	// ins(x,La,1);
	f[x]=En[x]-Bg[x]+1;
	f[x]+=Tree::qry(Bg[x]+1,En[x]);
	for(int i:S[x]) if(i^La) f[x]+=f[i];
	w[x]=-f[x];for(int i:S[x]) if(i^La) w[x]+=f[i];
	Tree::modify(Bg[x],w[x]);
	for(int i:S[x]) if(i^La) up[x]=MIN(up[x],up[i]);
}
void dfs4(int x,int La){
	for(int i:S[x]) if(i^La&&i^Sn[x]) dfs4(i,x),ins(i,x,-1,d[i]);
	if(Sn[x]) dfs4(Sn[x],x);
	for(int i:S[x]) if(i^La&&i^Sn[x]) ins(i,x,1,d[i]);
	for(auto i:Q[x]) Tree::Add(i.x,i.y,1);
	for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
	g[x]=n-(En[x]-Bg[x]+1);
	g[x]+=Tree::f[1]-Tree::qry(Bg[x],En[x]);
	// g[x]+=g[up[x]]+f[up[x]];
	g[x]-=f[x];
	// cerr<<x<<' '<<g[x]<<'\n';
}
void Make(int x,int La){g[x]+=g[up[x]]+f[up[x]];/*cerr<<g[x]<<'\n';*/if(!La) g[x]=0;for(int i:S[x]) if(i^La) Make(i,x);}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=1;i<n;i++) {
		int x,y;scanf("%d%d",&x,&y);
		S[x].eb(y);S[y].eb(x);
	}
	int Rt=1;
	dfs1(Rt,0);dfs2(Rt,Rt);
	int m;scanf("%d",&m);
	iota(up+1,up+n+1,1);
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		int Ls=LCA(x,y);up[x]=MIN(up[x],Ls);up[y]=MIN(up[y],Ls);
		// for(auto i:E) for(int j=i.fi;j<=i.se;j++) A[x][j]++,A[y][j]++,A[Ls][j]-=2;
		for(auto i:E) Q[x].eb((node){i.fi,i.se,d[Ls]}),Q[y].eb((node){i.fi,i.se,d[Ls]}),D[Ls].eb(i);
	}
	dfs3(Rt,0);ins(Rt,0,-1,0);dfs4(Rt,0);Make(Rt,0);
	for(i=1;i<=n;i++){
		ans[i]=g[i];for(int j:S[i]) if(j^fa[i]) ans[i]+=f[j];
		printf("%lld ",ans[i]);
	}
	cerr<<YAI<<'\n';
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 31520kb

input:

6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4

output:

6 9 9 10 7 7 

result:

ok single line: '6 9 9 10 7 7 '

Test #2:

score: 0
Accepted
time: 3ms
memory: 31948kb

input:

2
1 2
1
1 2

output:

1 1 

result:

ok single line: '1 1 '

Test #3:

score: 0
Accepted
time: 329ms
memory: 38056kb

input:

16384
9137 490
3442 7239
1621 6904
13769 10250
14672 12572
14906 9437
6163 12339
15244 12016
3022 8670
3211 9106
11966 14817
15798 15876
6423 7394
894 7695
13877 1983
16342 15158
13574 15932
15125 10722
6989 15683
10335 8801
12301 4246
6166 3893
9347 12073
7897 12195
6510 3101
4526 15385
7017 7001
4...

output:

34355 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...

result:

ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '

Test #4:

score: 0
Accepted
time: 2075ms
memory: 60128kb

input:

65536
44501 44259
59772 51161
51582 2027
2699 8610
5021 57211
60597 10270
29222 11423
38503 3833
52021 47503
47160 15296
61201 13465
20807 17239
7705 20234
32708 25663
7800 42265
29410 44963
32173 38920
49438 61282
25922 4342
40171 9819
12256 3995
41600 39383
57051 60932
44275 8351
8356 8295
3557 64...

output:

140178 136111 137025 136494 136304 137262 136598 135563 136530 135406 199677 137437 140282 136109 140127 136827 137235 136000 140738 139961 140081 142677 136544 201610 136181 136393 137013 137354 136855 135440 127050 136828 136781 137439 136518 185910 137170 136902 140686 136703 136847 137483 136337...

result:

ok single line: '140178 136111 137025 136494 13...63 136343 136858 137469 137325 '

Test #5:

score: -100
Time Limit Exceeded

input:

131071
28270 44685
69228 113487
10873 80967
30958 109340
53006 103488
49569 111875
65021 32861
83043 36671
73613 119374
22104 91373
31527 27737
19718 27803
90762 87148
4096 41649
79425 111516
111950 123500
94580 61416
30879 18640
71251 76344
61698 28557
104875 59268
130832 61334
110927 109064
114115...

output:


result: