QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#96757 | #6267. Triples of Cows | AFewSuns | 100 ✓ | 212ms | 50272kb | C++14 | 3.2kb | 2023-04-15 16:05:37 | 2023-04-15 16:05:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
ll n,head[400040],cnt=0,f[400040],d[400040],dep[400040],tg[400040],ans=0;
ll fa[400040],tot[400040],sum[400040],lz[400040],siz[400040],top[400040];
struct node{
ll nxt,to;
}e[800080];
void add(ll u,ll v){
e[++cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
ll find(ll x){
if(x==fa[x]) return x;
ll tmp=find(fa[x]);
if(fa[x]!=tmp) lz[x]+=lz[fa[x]];
return fa[x]=tmp;
}
void dfs(ll faa,ll u){
f[u]=faa;
dep[u]=dep[faa]+1;
go(u){
ll v=e[i].to;
if(v==faa) continue;
dfs(u,v);
}
}
ll calc(ll x){
find(x);
return lz[x]+lz[fa[x]];
}
void merge(ll x,ll y){
x=find(x);
y=find(y);
if(siz[x]<siz[y]) swap(x,y);
fa[y]=x;
siz[x]+=siz[y];
if(dep[top[x]]>dep[top[y]]) top[x]=top[y];
lz[y]-=lz[x];
}
int main(){
n=read();
fr(i,1,n-1){
ll u=read(),v=read();
d[u]++;
d[v]++;
add(u,n+i);
add(n+i,u);
add(n+i,v);
add(v,n+i);
}
dfs(0,1);
fr(i,1,2*n-1) fa[i]=i;
fr(i,1,2*n-1) siz[i]=1;
fr(i,1,2*n-1) top[i]=f[i];
fr(u,n+1,2*n-1){
tot[u]=2;
go(u){
ll v=e[i].to;
sum[u]+=d[v];
}
}
fr(i,1,n) ans+=d[i]*(d[i]-1);
fr(u,1,n){
writeln(ans);
ll all=0,nsum=0,tp=f[u],oth=0;
go(u){
ll v=find(e[i].to);
all+=tot[v]-1;
if(dep[tp]>dep[top[v]]) tp=top[v];
}
ans-=all*(all-1);
go(u){
ll v=find(e[i].to),tmp=all-tot[v]+1,sumv=sum[v];
if(top[v]){
sumv+=tg[top[v]];
if(f[top[v]]) sumv+=calc(f[top[v]]);
}
if(top[v]==tp){
oth=tmp;
if(top[v]) nsum-=tg[top[v]];
if(f[top[v]]) nsum-=calc(f[top[v]]);
}
nsum+=sumv-all-tot[v]+1;
nsum+=(tot[v]-1)*tmp;
ans+=((tmp-1)*(tmp-1)-(tmp-1))*(tot[v]-1);
ans+=2*(tmp-1)*(sumv-all);
}
go(u){
ll v=find(e[i].to),tmp=all-tot[v]+1;
lz[v]+=tmp-1;
}
go(u) merge(u,e[i].to);
ll fu=find(u);
tot[fu]=all;
sum[fu]=nsum;
if(top[fu]){
tg[top[fu]]+=oth-1;
sum[fu]-=oth-1;
if(f[top[fu]]) sum[find(f[top[fu]])]+=oth-1;
}
}
}
詳細信息
Test #1:
score: 5
Accepted
time: 4ms
memory: 17620kb
input:
3 1 2 2 3
output:
2 0 0
result:
ok 3 lines
Test #2:
score: 5
Accepted
time: 0ms
memory: 17640kb
input:
4 1 2 1 3 1 4
output:
6 6 0 0
result:
ok 4 lines
Test #3:
score: 5
Accepted
time: 5ms
memory: 17620kb
input:
5 3 5 5 1 1 4 1 2
output:
8 10 2 0 0
result:
ok 5 lines
Test #4:
score: 5
Accepted
time: 1ms
memory: 17768kb
input:
500 11 3 327 355 314 180 428 417 349 438 319 16 322 365 430 4 116 384 95 469 476 16 96 444 330 323 282 380 179 365 416 151 361 34 422 417 122 440 206 264 169 381 237 420 167 47 118 421 442 149 474 112 135 359 230 221 178 391 39 464 326 105 198 24 33 419 455 240 120 50 406 134 124 32 186 424 6 157 21...
output:
1970 1960 1958 1956 2050 2046 2044 2042 2040 2038 2034 2032 2028 2026 2022 2020 2076 2080 2090 2074 2066 2058 2056 2054 2058 2048 2046 2048 2046 2044 2042 2040 2052 2050 2082 2070 2068 2108 2106 2102 2100 2106 2104 2110 2108 2106 2120 2126 2122 2134 2166 2162 2130 2122 2120 2114 2106 2102 2100 2094 ...
result:
ok 500 lines
Test #5:
score: 5
Accepted
time: 5ms
memory: 17764kb
input:
500 117 273 162 26 468 332 44 21 227 163 368 215 241 403 60 319 297 303 376 139 14 134 438 452 8 65 195 48 230 188 475 485 152 136 35 375 272 487 72 242 208 180 330 157 75 487 278 159 110 497 364 339 255 73 405 16 463 368 26 320 226 377 149 410 240 436 439 56 43 422 37 287 186 228 347 248 294 435 67...
output:
1952 1950 1942 1932 1934 1928 1920 1914 1912 1910 1908 1906 1904 1898 1892 1932 2080 2070 2216 2212 2210 2238 2236 2234 2232 2230 2242 2330 2326 2314 2312 2324 2322 2372 2386 2384 2394 2392 2388 2386 2380 2378 2376 2394 2392 2390 2396 2402 2412 2410 2406 2402 2400 2394 2406 2396 2538 2534 2588 2586 ...
result:
ok 500 lines
Test #6:
score: 5
Accepted
time: 2ms
memory: 20140kb
input:
5000 192 2280 866 1993 3318 2270 866 4634 1062 1191 1616 1183 3798 951 866 1590 4607 3400 866 4962 1816 4504 468 325 4569 1736 866 1130 2690 866 4389 866 4240 1120 1932 1614 2487 3373 866 1903 1261 2826 219 1064 44 4360 866 1333 866 1636 2726 2577 2130 866 4693 4818 1190 866 3319 2069 1424 240 1113 ...
output:
4926576 4926574 4926572 4926566 4926564 4926560 4926554 4922120 4922118 4917686 4917684 4917680 4913250 4908822 4908820 4904394 4904356 4904380 4904378 4904376 4904374 4904372 4904370 4899946 4899970 4895548 4895546 4891126 4886708 4886706 4886704 4882288 4877874 4877872 4877870 4877868 4873456 4869...
result:
ok 5000 lines
Test #7:
score: 5
Accepted
time: 2ms
memory: 18212kb
input:
5000 1026 19 4489 1374 1374 976 2917 317 2875 19 3741 2419 3056 444 19 1591 1983 19 4825 1374 2444 1374 2937 19 1374 2301 1246 1374 19 4829 19 3893 1374 3084 19 2482 19 3772 19 2434 4565 2642 3810 3291 1650 4033 1374 3824 4103 3281 19 852 19 2561 1018 112 1374 2096 1661 1374 19 280 19 3695 356 2671 ...
output:
7126950 7122520 7118092 7118090 7113664 7113652 7113650 7110676 7107704 7103280 7100310 7095888 7091468 7088500 7084082 7079666 7075252 7070840 7066430 10708504626 10708504624 10708504634 10693938346 10679385276 10664845418 10664842452 10650315800 10650315798 10650315796 10635802344 10635799380 1062...
result:
ok 5000 lines
Test #8:
score: 5
Accepted
time: 1ms
memory: 18212kb
input:
5000 3656 2617 1546 2617 3883 2531 487 302 2617 1655 2617 3150 684 4158 2641 4762 2552 2300 2617 2415 3766 1485 3401 155 2458 2617 1941 1219 2617 4612 990 4670 4551 1784 2617 3315 2617 3058 2617 4611 3379 2555 1745 1914 2617 4652 3820 1368 557 4236 4777 2667 774 4214 4592 961 3468 754 539 3369 2390 ...
output:
5011042 5006584 5006580 5006538 5002082 5002074 4997620 4997618 4997612 4997618 4997616 4993164 4988714 4988712 4988710 4988840 4984392 4984110 4984106 4979660 4975216 4970774 4970770 4970768 4970766 4970762 4966322 4961884 4961904 4957468 4953034 4948602 4948598 4948588 4944158 4939730 4939728 4935...
result:
ok 5000 lines
Test #9:
score: 5
Accepted
time: 1ms
memory: 18164kb
input:
5000 1963 1714 2089 1714 1958 1714 1174 516 2468 1714 4013 780 542 1714 1714 921 1714 494 2799 3447 1714 4167 2663 1377 4753 58 3643 4557 1714 623 1714 2198 4997 1992 1518 722 1714 1367 2723 4870 4103 2072 1714 4384 4299 2533 433 969 1714 4644 1253 1652 4838 2735 1508 1714 596 4817 2465 3850 3287 23...
output:
5108150 5103636 5099124 5099122 5099116 5099086 5099084 5099076 5094566 5094564 5094562 5094560 5094556 5090048 5085542 5081038 5076536 5076532 5076490 5071990 5067492 5067490 5062994 5058500 5054008 5049518 5049516 5049514 5045026 5045066 5045064 5040578 5040626 5036142 5036140 5031658 5027178 5022...
result:
ok 5000 lines
Test #10:
score: 5
Accepted
time: 2ms
memory: 20316kb
input:
5000 1952 4980 1776 4362 3887 1033 1033 4047 523 4980 357 1033 1033 941 4631 1033 1033 3253 960 4980 1033 2582 4980 887 984 2694 3715 4956 4728 1376 4980 3197 2996 4357 1490 1033 1033 2798 9 1033 4980 1084 1033 3349 2554 4980 204 1037 1033 4660 3004 1249 3817 2960 1033 1761 1033 2152 1033 1740 1033 ...
output:
7200814 7197878 7193392 7190458 7190456 7187524 7183040 7178558 7175628 7171148 7168220 7163742 7159266 7154792 7151866 7147394 7147226 7142756 7138288 7133822 7130898 7126434 7126428 7121966 7117506 7113048 7108592 7108598 7105676 7101222 7096770 7092320 7087872 7087870 7087868 7087866 7084946 7080...
result:
ok 5000 lines
Test #11:
score: 5
Accepted
time: 212ms
memory: 49776kb
input:
200000 180343 93112 133794 25463 15259 32390 161405 75514 53906 75514 31334 75514 145757 75514 91720 75514 113316 10952 75514 24136 30812 144626 84587 109632 28810 104546 75514 162784 73000 185642 75514 12153 75514 30841 74493 76012 177125 150153 100571 107545 118366 139210 10965 75514 21955 75514 7...
output:
7907948828 7907771022 7907771020 7907771018 7907771016 7907593212 7907593202 7907593200 7907593198 7907593196 7907593194 7907593192 7907593200 7907593198 7907415396 7907237596 7907059798 7907059582 7907059590 7907059588 7906881792 7906881790 7906703996 7906526204 7906526202 7906348412 7906170624 790...
result:
ok 200000 lines
Test #12:
score: 5
Accepted
time: 169ms
memory: 48692kb
input:
200000 156524 164378 63451 181093 142236 156524 156524 91309 195366 63451 63451 54126 62067 43431 48083 17306 156524 139870 156524 79853 63451 118039 63451 10162 116377 114109 82955 48083 17725 63451 1075 156524 77519 156524 156524 118428 63451 126448 108533 156524 133574 156524 63451 10239 119214 1...
output:
11749107100 11748929116 11748810644 11748774978 11748774704 11748656234 11748537766 11748419300 11748300836 11748300562 11748122580 11747944600 11747826138 11747648160 11747470184 11747292210 11747173750 11746995778 11746817808 11746699350 11746521382 11746343416 11746343414 11746165450 11748102948 ...
result:
ok 200000 lines
Test #13:
score: 5
Accepted
time: 169ms
memory: 48780kb
input:
200000 128878 43530 11660 61275 93778 135514 128878 65607 105027 128878 99196 126852 121316 119378 12994 121964 128878 157185 186752 128878 66811 97145 166913 95469 188773 91487 128878 164320 52546 128878 173916 128878 180121 126852 174374 128878 123398 126852 123003 128878 109982 128878 106656 1288...
output:
11440362682 11440184680 11440006680 11439828682 11439650686 11439472692 11439354062 11439176070 11439176068 11439176066 11439057438 11438879448 11438701460 11438523474 11438345490 11438167508 11438167506 11437989526 11437989516 11437811538 11437633562 11437455588 11437455584 11437336958 11437158986 ...
result:
ok 200000 lines
Test #14:
score: 5
Accepted
time: 141ms
memory: 49040kb
input:
200000 75292 57657 154653 141350 140800 57657 57657 162746 124811 59959 154653 89884 57657 25957 60896 67370 183207 26852 57657 43172 188291 57657 154653 102124 57657 157547 132684 57657 154653 143124 124811 188592 57657 109286 66896 87163 57657 30111 154653 131248 107225 57657 139132 29848 181221 1...
output:
11764531042 11764353072 11764175104 11763997138 11763878524 11763759912 11763641302 11763634162 11763515554 11763337590 11763159628 11762981668 11762803710 11762685104 11762507148 11762388544 11762353088 11762175134 11761997182 11761878580 11761700630 11761665176 11761487228 11761309282 11761131338 ...
result:
ok 200000 lines
Test #15:
score: 5
Accepted
time: 197ms
memory: 48804kb
input:
200000 48508 52931 115469 53334 53334 109332 55615 111128 160153 129069 81733 149640 69172 127972 53334 71755 107633 53334 92200 144859 191346 61711 192310 131522 144360 89737 112809 69429 24034 53334 8244 53334 134631 53334 53334 157868 179139 39842 112773 53334 131063 78546 95501 143642 50916 5333...
output:
7974890890 7974712844 7974534800 7974356758 7974178718 7974000680 7973822644 7973644610 7973632734 7973454702 7973454700 7973276670 7973098642 7973091582 7973079708 7973079706 7973079702 7973079888 7973072830 7972894804 7972894798 7972894794 7972716770 7972716758 7972538736 7972360716 7972182698 797...
result:
ok 200000 lines
Test #16:
score: 5
Accepted
time: 192ms
memory: 48752kb
input:
200000 189585 140451 189585 21397 97507 124392 189551 66778 35172 110107 34572 137133 189585 175319 68631 185609 189585 113509 195998 52967 125268 189585 189585 38545 195154 62941 22458 189585 111738 150491 181476 40967 189585 175600 183092 164108 2191 91624 189585 98869 104639 189585 189585 11160 1...
output:
7948844896 7948844894 7948666996 7948667060 7948489164 7948311270 7948133378 7948121550 7948121548 7947943658 7947943946 7947943944 7947766056 7947588170 7947588168 7947588166 7947410282 7947232400 7947054520 7946876642 7946698766 7946698764 7946520890 7946343018 7946343016 7946165146 7946165138 794...
result:
ok 200000 lines
Test #17:
score: 5
Accepted
time: 152ms
memory: 48624kb
input:
200000 52744 169423 21958 49886 107574 14898 179360 193309 52744 173255 11649 194058 52744 37299 185040 52744 173083 16183 45172 52744 111564 52744 118979 40378 16515 40367 116092 15886 21781 52744 52744 18485 155320 52744 164746 118979 52744 178385 119944 52744 183596 148338 97026 100365 154834 159...
output:
7949417986 7949414460 7949414456 7949236732 7949059010 7948881290 7948881350 7948703632 7948525916 7948525914 7948348200 7948170488 7948170514 7948163404 7947985694 7947985456 7947807748 7947807942 7947807938 7947630232 7947452528 7947452526 7947274824 7947097124 7947097136 7947097134 7947097130 794...
result:
ok 200000 lines
Test #18:
score: 5
Accepted
time: 169ms
memory: 50272kb
input:
200000 98188 97568 97568 139023 97568 145232 43972 86482 97568 76922 152654 113293 97568 187093 14560 97568 130417 25367 180256 26394 70931 175568 97568 46170 102988 88140 152897 80698 151625 97568 28288 28935 97568 184813 46246 97568 126910 118530 120407 37832 97568 130045 101579 48512 176793 92123...
output:
7947926838 7947926848 7947926846 7947926886 7947926884 7947748778 7947570674 7947570672 7947392570 7947392568 7947392566 7947392564 7947392562 7947392560 7947214460 7947214458 7947214456 7947214454 7947214452 7947036354 7947029294 7946851198 7946673104 7946495012 7946495010 7946495008 7946495006 794...
result:
ok 200000 lines
Test #19:
score: 5
Accepted
time: 164ms
memory: 49112kb
input:
200000 82514 160608 129118 74477 117781 160275 32607 77450 33384 83542 177617 190138 33384 6337 94051 17548 75494 139091 22526 33384 194668 33384 9010 33384 32463 33384 33384 81726 33384 199774 68788 33384 52181 175598 18372 33384 160069 33384 75532 3294 154793 166505 33384 84585 52141 162634 138451...
output:
7901247652 7901247650 7901069904 7901069902 7901069898 7900892154 7900714412 7900714410 7900714408 7900536668 7900536666 7900358928 7900181192 7900181188 7900003454 7899825722 7899825720 7899647990 7899648012 7899470284 7899468526 7899468528 7899290802 7899290800 7899290798 7899290796 7899290794 789...
result:
ok 200000 lines
Test #20:
score: 5
Accepted
time: 179ms
memory: 48816kb
input:
200000 123057 85473 181057 139168 139374 155981 97580 66941 139374 26235 92577 28176 53567 44615 139374 158256 139374 111698 139374 7486 167825 194890 39334 139374 124253 139374 99441 512 41950 157947 45135 122712 19652 139374 145589 139374 77187 106020 111608 128762 139374 163048 67917 139374 51654...
output:
7939722716 7939722714 7939722724 7939544582 7939544572 7939544570 7939544558 7939544784 7939544746 7939544744 7939366604 7939366602 7939188464 7939010328 7938832194 7938654062 7938654060 7938475930 7938475918 7938297790 7938119664 7938119826 7937941702 7937763580 7937763566 7937585446 7937585444 793...
result:
ok 200000 lines