QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210350#4839. Smaller LCA275307894aWA 513ms112804kbC++142.2kb2023-10-11 11:40:112023-10-11 11:40:12

Judging History

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

  • [2023-10-11 11:40:12]
  • 评测
  • 测评结果:WA
  • 用时:513ms
  • 内存:112804kb
  • [2023-10-11 11:40:11]
  • 提交

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
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=4e5+5,M=N*4,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n;ll ans[N];
vector<int> S[N];
int Si[N],Sn[N],d[N],fa[N],Tp[N];
void dfs1(int x,int La){
	Si[x]=1;d[x]=d[La]+1;fa[x]=La;
	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){
	Tp[x]=La;if(!Sn[x]) return;dfs2(Sn[x],La);for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);
}
int LCA(int x,int y){
	while(Tp[x]^Tp[y]) d[Tp[x]]<d[Tp[y]]&&(swap(x,y),0),x=fa[Tp[x]];
	return d[x]<d[y]?x:y;
}
int Jp(int x,int y){
	while(d[fa[Tp[y]]]>d[x]) y=fa[Tp[y]];
	return Tp[x]^Tp[y]?Tp[y]:Sn[x];
}
namespace BIT{
	int f[N];void add(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}
	int qry(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
}
vector<pii> Q[N];
void dfs(int x,int La){
	for(auto i:Q[x]) BIT::add(i.fi,i.se);
	for(int i:S[x]) if(i^La){
		int w=BIT::qry(x);dfs(i,x);w=BIT::qry(x)-w;
		ans[x]+=w;ans[i]-=w;
	}
}
void make(int x,int La){
	for(int i:S[x]) if(i^La) ans[i]+=ans[x],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].emplace_back(y);S[y].emplace_back(x);}
	dfs1(1,0);dfs2(1,1);
	for(i=1;i<=n;i++) {
		for(j=i+1;1ll*i*j<n;j++){
			int w=i*j+1,Ls=LCA(i,j),px=(i^Ls?Jp(Ls,i):0),py=(j^Ls?Jp(Ls,j):0);//cerr<<i<<' '<<j<<' '<<Ls<<'\n';
			if(Ls>=w){
				ans[1]++;ans[px]--;ans[py]--;
			}
			if(i^Ls) Q[i].emplace_back(w,1),Q[px].emplace_back(w,-1);
			if(j^Ls) Q[j].emplace_back(w,1),Q[px].emplace_back(w,-1);
		}
	}
	dfs(1,0);make(1,0);
	for(i=1;i<=n;i++) printf("%lld\n",1ll*n*(n+1)/2-ans[i]);
}
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: 3ms
memory: 31576kb

input:

5
1 2
4 2
2 5
3 5

output:

15
15
15
15
14

result:

ok 5 number(s): "15 15 15 15 14"

Test #2:

score: -100
Wrong Answer
time: 513ms
memory: 112804kb

input:

300000
40632 143306
32259 40632
225153 143306
269774 225153
289668 40632
191636 269774
85717 191636
58564 191636
156509 143306
289939 40632
247103 269774
40257 40632
98149 289668
142277 143306
291616 40257
46813 225153
56324 143306
277154 142277
53903 289668
114266 32259
152231 58564
241151 152231
4...

output:

44999437117
44999538134
44999550548
44999549589
44999050067
44999421278
44999337570
44999085096
44999027893
44999083621
44999537835
44999091375
44999217363
44999285940
44999372570
44999371501
44999074871
44999250575
44999261885
44999078953
44999493067
44999246436
44999365029
44999082164
44999337122
...

result:

wrong answer 2nd numbers differ - expected: '44999604051', found: '44999538134'