QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210355 | #4839. Smaller LCA | 275307894a | AC ✓ | 571ms | 126344kb | C++14 | 2.2kb | 2023-10-11 11:45:36 | 2023-10-11 11:45:36 |
Judging History
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[py].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';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 29996kb
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: 0
Accepted
time: 541ms
memory: 116844kb
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 44999604051 44999615557 44999614574 44999052534 44999484860 44999371316 44999125588 44999026878 44999118903 44999600090 44999126307 44999249359 44999307961 44999422135 44999360213 44999109672 44999283107 44999293969 44999113471 44999549862 44999278828 44999353626 44999122409 44999352565 ...
result:
ok 300000 numbers
Test #3:
score: 0
Accepted
time: 564ms
memory: 119504kb
input:
299999 97687 248627 80337 97687 77032 80337 92616 80337 106631 248627 248726 77032 176093 92616 73262 248726 233147 80337 39942 248726 15921 176093 188366 248627 31058 80337 239076 73262 44766 233147 10344 176093 192127 233147 109285 80337 6814 176093 239926 97687 204083 77032 252211 15921 5158 7703...
output:
44999344660 44999363522 44999206495 44999093451 44999362732 44999276207 44999352410 44999343961 44999149170 44999277616 44999158043 44999332131 44999288440 44999317886 44999301651 44999266803 44999346932 44999241092 44999298075 44999129430 44999277318 44999272323 44999209973 44999271917 44999269931 ...
result:
ok 299999 numbers
Test #4:
score: 0
Accepted
time: 571ms
memory: 117608kb
input:
300000 282498 119808 46316 119808 58818 119808 179940 119808 6601 282498 16229 46316 25007 58818 180795 16229 83945 179940 246574 179940 268478 179940 134193 246574 164637 6601 78275 83945 241804 119808 177735 6601 225133 134193 188943 179940 36121 188943 148019 164637 223449 180795 41835 188943 237...
output:
44999540514 44999412634 44999309802 44999471134 44999211366 44999458009 44999479974 44999281366 44999372403 44999448719 44999365824 44999443217 44999455734 44999482977 44999585712 44999540082 44999475151 44999453573 44999399100 44999346705 44999372230 44999256996 44999368064 44999452600 44999473178 ...
result:
ok 300000 numbers
Test #5:
score: 0
Accepted
time: 534ms
memory: 116516kb
input:
299999 173205 142232 104374 142232 39513 104374 67867 104374 42519 173205 145713 39513 190264 104374 240190 67867 220708 240190 237545 67867 211015 220708 73889 39513 126319 220708 38274 67867 257538 240190 260471 237545 44453 142232 24527 142232 23487 173205 174569 173205 158023 173205 100347 42519...
output:
44999145790 44999091319 44999049858 44999174810 44998980768 44999252786 44999144473 44998983973 44998953014 44999259775 44998949495 44999055625 44998909201 44998956878 44999261370 44998927703 44999167393 44999140464 44998905939 44998940216 44998919447 44999239170 44999100182 44998941726 44999273329 ...
result:
ok 299999 numbers
Test #6:
score: 0
Accepted
time: 562ms
memory: 115780kb
input:
299999 144140 64463 84381 64463 275996 144140 144612 144140 22940 275996 97432 275996 258170 64463 268975 84381 113121 268975 74024 258170 162810 275996 222898 74024 218308 22940 294515 64463 4344 218308 287764 74024 73585 97432 116481 287764 204008 144140 125526 73585 133816 294515 31053 258170 107...
output:
44999005167 44999209294 44998941343 44998935023 44999171993 44999086771 44999206524 44999091272 44998923732 44999092407 44999090745 44998910337 44998836857 44999087877 44999105320 44998879519 44998983003 44998798532 44998760921 44999084330 44999064280 44999054760 44999103030 44999130090 44999053488 ...
result:
ok 299999 numbers
Test #7:
score: 0
Accepted
time: 461ms
memory: 119328kb
input:
300000 17050 75638 59628 17050 250487 75638 222372 17050 83877 75638 252612 59628 223823 83877 71675 252612 264309 223823 56862 222372 250608 83877 112630 223823 122103 250608 148130 56862 32428 112630 181607 56862 230036 148130 99321 230036 211188 181607 272235 148130 57324 272235 260876 272235 191...
output:
44999618044 44999147094 44999677093 44999732634 44999460409 44999160790 44999579139 44999467908 44999184681 44999199263 44999231239 44999488195 44999805266 44999547232 44999707240 44999537930 44999505219 44999563833 44999465777 44999426341 44999557653 44999794024 44999548625 44999794023 44999570124 ...
result:
ok 300000 numbers
Test #8:
score: 0
Accepted
time: 475ms
memory: 119072kb
input:
299999 221069 282534 214173 282534 24237 221069 204787 282534 245620 204787 136288 221069 209773 245620 287963 245620 292336 24237 21383 292336 172534 209773 127524 209773 16214 21383 87226 287963 170040 172534 103312 87226 52385 127524 140929 170040 193496 52385 203825 87226 115524 170040 220799 52...
output:
44999572210 44999458670 44998911277 44999184039 44999206776 44999443592 44999417299 44999356502 44999179829 44999237265 44999572056 44999206883 44998942302 44999260955 44998835660 44999452577 44999346141 44999194483 44999380831 44998863337 44998893184 44999520307 44999572157 44999173592 44999110483 ...
result:
ok 299999 numbers
Test #9:
score: 0
Accepted
time: 444ms
memory: 119748kb
input:
300000 8889 36706 157543 8889 104012 8889 62314 157543 242859 36706 149378 8889 10456 157543 29565 104012 131101 149378 22513 131101 90461 22513 40078 131101 141748 10456 72882 22513 176272 22513 90154 141748 215195 90154 43336 40078 296478 90154 128801 90154 149034 128801 102954 149034 254677 29647...
output:
44999724123 44999887080 44999879556 44999518077 44999609913 44999556275 44999588000 44999593838 44999680913 44999380889 44999880288 44999657021 44999383706 44999144202 44999478288 44999199032 44999614075 44999790343 44999766790 44999445094 44999424718 44999260077 44999887302 44999847443 44999676358 ...
result:
ok 300000 numbers
Test #10:
score: 0
Accepted
time: 485ms
memory: 122776kb
input:
299998 29430 279377 87865 279377 33400 87865 149559 33400 218448 149559 274422 87865 62550 149559 215553 274422 239913 274422 107224 149559 289982 218448 256498 239913 143232 239913 103543 289982 90558 107224 254844 143232 7345 90558 139410 143232 171957 90558 85463 139410 207261 171957 128676 13941...
output:
44998919397 44998530568 44998745272 44999059683 44999013065 44999181214 44999129502 44999154742 44999172744 44998691167 44998858765 44999070146 44998807013 44998859372 44998761740 44999120708 44998877194 44998808804 44998912953 44998550644 44999009720 44998818725 44999061235 44998695918 44999085009 ...
result:
ok 299998 numbers
Test #11:
score: 0
Accepted
time: 499ms
memory: 125820kb
input:
299999 279808 219366 64566 279808 294679 64566 192527 294679 290866 294679 282142 64566 112420 290866 29858 290866 269073 112420 19694 112420 66844 19694 42940 112420 142231 112420 58837 142231 295419 58837 9002 19694 4808 142231 7272 9002 30675 4808 62872 30675 81916 7272 260542 62872 146224 62872 ...
output:
44999374155 44999307472 44999179996 44999188269 44999102614 44999300805 44998993219 44999018542 44999252456 44999480338 44999203231 44998930625 44999347959 44999487732 44999529114 44998903631 44999333440 44999238520 44999388913 44999277968 44999288307 44998958543 44999163087 44999009462 44999226099 ...
result:
ok 299999 numbers
Test #12:
score: 0
Accepted
time: 332ms
memory: 118820kb
input:
299998 150616 76335 88273 150616 206635 76335 200072 206635 38950 150616 298642 206635 179779 200072 246700 38950 231698 88273 202098 76335 105468 38950 265562 38950 173901 38950 211307 200072 159253 88273 131738 150616 17278 76335 103492 76335 173877 206635 10117 38950 294264 38950 9644 206635 2619...
output:
44998690423 44998587106 44998552667 44998705776 44998783481 44998918153 44998838542 44998686949 44998913912 44998683184 44998681815 44998501008 44998499683 44998508345 44998507393 44998496703 44998505823 44998505170 44998676050 44998909247 44998770030 44998834748 44998674671 44998908611 44998502057 ...
result:
ok 299998 numbers
Test #13:
score: 0
Accepted
time: 350ms
memory: 122788kb
input:
300000 62153 119940 226708 62153 55561 62153 97490 119940 267543 62153 151359 62153 208097 226708 34037 62153 221025 267543 49672 55561 105826 97490 190961 119940 150215 62153 131328 97490 181843 62153 21558 62153 131191 226708 286431 267543 272999 97490 82627 62153 71629 97490 223118 97490 173750 9...
output:
44999490977 44999581101 44999339839 44999579162 44999545119 44999703946 44999296656 44999292608 44999534458 44999700242 44999532035 44999699316 44999698959 44999403875 44999688337 44999688078 44999528187 44999560206 44999276201 44999697464 44999526843 44999526583 44999526346 44999686783 44999273338 ...
result:
ok 300000 numbers
Test #14:
score: 0
Accepted
time: 360ms
memory: 121020kb
input:
299998 135922 237786 295644 135922 262303 295644 265807 237786 212115 265807 113095 262303 228408 265807 25124 295644 228236 262303 257454 262303 211200 265807 259284 262303 102582 237786 214954 237786 53868 262303 243618 212115 278431 262303 190297 135922 79400 212115 10680 295644 207199 135922 198...
output:
44998307177 44998533670 44998511017 44998187410 44998492894 44998122262 44998161933 44998111332 44998070905 44998049505 44998478066 44998141914 44998042682 44998139389 44998096031 44998038418 44998057006 44998056138 44998055360 44998091660 44998054028 44998090467 44998133460 44998032259 44998052003 ...
result:
ok 299998 numbers
Test #15:
score: 0
Accepted
time: 338ms
memory: 123356kb
input:
299999 150553 278809 170492 150553 229941 150553 241638 278809 84806 170492 24747 241638 171095 84806 244435 278809 158820 229941 120598 229941 217325 229941 202400 170492 62375 278809 239168 84806 119263 84806 107931 170492 281318 241638 17724 278809 5221 84806 25640 84806 174770 278809 227149 2416...
output:
44998747754 44998741449 44998703125 44998566526 44998672467 44998664802 44998786139 44998655221 44998830891 44998778833 44998827849 44998887345 44998825743 44998642903 44998824199 44998521219 44998771812 44998822527 44998518834 44998429416 44998821332 44998428149 44998427598 44998883811 44998635676 ...
result:
ok 299999 numbers
Test #16:
score: 0
Accepted
time: 342ms
memory: 118936kb
input:
300000 268282 130589 137710 130589 93460 137710 230491 130589 225183 137710 212453 268282 207913 130589 87858 130589 216796 93460 279662 230491 72760 225183 143429 268282 37775 130589 66916 130589 298071 268282 91115 225183 131823 268282 156244 137710 900 93460 109398 230491 242948 230491 79191 2682...
output:
44999281735 44999366146 44999197401 44999108867 44999371737 44999368622 44999154509 44999109189 44999147361 44999291460 44999100043 44999289165 44999288283 44999067708 44999066611 44999092421 44999358543 44999064050 44999089774 44999062769 44999357496 44999357294 44999132131 44999283427 44999060464 ...
result:
ok 300000 numbers
Test #17:
score: 0
Accepted
time: 391ms
memory: 123272kb
input:
299999 143120 236256 148524 236256 200355 236256 36612 143120 266835 236256 238942 236256 96320 148524 289074 236256 141286 236256 194154 143120 198985 148524 5485 236256 186492 236256 151237 148524 150634 236256 284380 236256 249188 143120 141549 236256 205557 148524 288282 143120 106319 236256 112...
output:
44999014097 44999153762 44998915081 44999377507 44999364176 44998890327 44999111383 44998822358 44998820371 44998646022 44998879076 44998816395 44999247378 44998655581 44998814010 44998653471 44999364533 44999028363 44998873391 44998811624 44998811284 44998948277 44998810691 44998871762 44998810193 ...
result:
ok 299999 numbers
Test #18:
score: 0
Accepted
time: 396ms
memory: 118340kb
input:
299998 118462 77330 106795 118462 153182 106795 26555 106795 23658 106795 157357 106795 11915 118462 203374 106795 168323 118462 106742 77330 171860 118462 227212 118462 75338 106795 110268 77330 124506 106795 253862 118462 150397 77330 98003 77330 215024 118462 260493 118462 283012 118462 179091 11...
output:
44999331297 44999273639 44999331468 44999047606 44999037182 44999050031 44999189112 44999000737 44998999092 44998587594 44999015801 44998995801 44999051726 44999023452 44999016873 44998993333 44999022106 44999050074 44999131221 44999049644 44999049460 44999119707 44999333219 44999020273 44999129496 ...
result:
ok 299998 numbers
Test #19:
score: 0
Accepted
time: 399ms
memory: 122792kb
input:
300000 7713 268697 109798 7713 214823 7713 209700 109798 198009 268697 90616 109798 248974 109798 217891 109798 2919 268697 289625 7713 230098 7713 38379 109798 82546 7713 143115 109798 238446 109798 258032 109798 134218 109798 279009 7713 91097 7713 274170 268697 112624 7713 172812 7713 176525 7713...
output:
44999143485 44999709847 44998964354 44999552973 44999594095 44999707455 44999593654 44999564285 44998904644 44999444525 44999564037 44999442695 44999441991 44999593103 44999440865 44999440408 44999440004 44999434747 44999592958 44999522317 44999438774 44998887002 44999289657 44999656610 44999328462 ...
result:
ok 300000 numbers
Test #20:
score: 0
Accepted
time: 369ms
memory: 126344kb
input:
299999 220744 130620 175965 130620 36292 175965 235084 220744 142692 130620 211978 130620 159885 175965 97554 130620 253362 220744 30758 175965 237264 175965 295575 130620 130534 220744 88884 130620 93151 175965 122607 130620 171318 220744 169736 220744 229323 220744 162185 175965 88905 175965 24759...
output:
44998896158 44998942515 44998990095 44998898524 44998719563 44998918962 44998706949 44999302922 44998961069 44998697489 44999278192 44998869196 44998899846 44999358456 44998866263 44998954719 44999278132 44999225071 44999358660 44998953086 44998862912 44999268921 44999127378 44998901444 44998951780 ...
result:
ok 299999 numbers
Test #21:
score: 0
Accepted
time: 381ms
memory: 123252kb
input:
300000 146946 294933 286134 294933 87613 294933 252628 146946 98021 286134 235659 294933 2000 286134 4199 286134 155709 294933 57448 294933 254917 286134 235643 146946 123086 286134 127752 294933 173711 146946 30513 286134 12191 294933 120701 286134 77529 286134 290568 294933 263323 146946 200178 28...
output:
44999394841 44998955621 44998919210 44999403875 44999667250 44999060816 44999676964 44999393640 44999679758 44999262590 44999614395 44999348297 44999182207 44998844271 44999257692 44998841716 44998840664 44999680206 44998823677 44999424339 44999254893 44998821561 44998836273 44998820443 44998819952 ...
result:
ok 300000 numbers
Test #22:
score: 0
Accepted
time: 3ms
memory: 28220kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 0ms
memory: 30180kb
input:
2 1 2
output:
3 3
result:
ok 2 number(s): "3 3"
Test #24:
score: 0
Accepted
time: 0ms
memory: 31376kb
input:
3 1 2 2 3
output:
6 6 6
result:
ok 3 number(s): "6 6 6"