QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #807205 | #7961. 一棵树 | dxbt | AC ✓ | 359ms | 84304kb | C++14 | 1.4kb | 2024-12-09 20:01:43 | 2024-12-09 20:01:43 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define ep emplace_back
using namespace std;
typedef long long ll;
constexpr int N=5e5;
priority_queue<int,vector<int>,less<int> > q[N+9];
int n,k;int tag[N+9];
int gen;
struct node
{
int nxt;
int to;
}ed[N*2+9];
int head[N+9];int tot;
void adde(int x,int y)
{
ed[++tot].to=y;
ed[tot].nxt=head[x];
head[x]=tot;
}
int dfs1(int x,int fa)
{
int sz=1,mx=0;
for(int i=head[x];i;i=ed[i].nxt)
if(ed[i].to!=fa)
{
int t=dfs1(ed[i].to,x);
sz+=t;
mx=max(mx,t);
}
if(sz>n/2&&mx<=n/2) gen=x;
return sz;
}
void dfs(int x,int fa)
{
q[x].push(0);
for(int i=head[x],u=ed[i].to;i;u=ed[i=ed[i].nxt].to)
{
if(u==fa)continue;
dfs(u,x);
if(q[u].size()>q[x].size())swap(q[x],q[u]),swap(tag[x],tag[u]);
while(!q[u].empty())q[x].push(q[u].top()+tag[u]-tag[x]),q[u].pop();
}
if(fa)
{
while(q[x].size()>(k+1)/2) q[x].pop();
tag[x]-=2;
if(k&1&&q[x].size()==(k+1)/2)
{
int p=q[x].top();
q[x].pop();
q[x].push(p+2);
}
}
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cin>>n>>k;
F(i,1,n-1)
{
int u,v;
cin>>u>>v;
adde(u,v);
adde(v,u);
}
dfs1(1,0);
dfs(gen,0);
ll ans=1ll*(n-1)*k;
while(q[gen].size()>k)q[gen].pop();
F(i,1,k)
{
ans+=q[gen].top()+tag[gen];
q[gen].pop();
}
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 299ms
memory: 59216kb
input:
499991 31473 1 2 2 3 1 4 2 5 4 6 4 7 6 8 4 9 8 10 6 11 9 12 10 13 10 14 1 15 14 16 3 17 14 18 12 19 13 20 11 21 16 22 16 23 20 24 5 25 16 26 18 27 8 28 15 29 27 30 27 31 26 32 21 33 3 34 27 35 33 36 25 37 22 38 11 39 11 40 17 41 25 42 3 43 3 44 2 45 35 46 25 47 5 48 6 49 41 50 42 51 1 52 39 53 14 54...
output:
15734930984
result:
ok single line: '15734930984'
Test #2:
score: 0
Accepted
time: 144ms
memory: 60324kb
input:
499993 461706 1 2 2 3 3 4 1 5 3 6 3 7 7 8 5 9 5 10 7 11 10 12 9 13 13 14 12 15 13 16 15 17 14 18 17 19 16 20 15 21 16 22 17 23 22 24 20 25 23 26 25 27 27 28 28 29 25 30 29 31 30 32 31 33 33 34 33 35 32 36 36 37 35 38 33 39 34 40 35 41 41 42 40 43 42 44 39 45 40 46 41 47 43 48 44 49 46 50 49 51 50 52...
output:
195357165512
result:
ok single line: '195357165512'
Test #3:
score: 0
Accepted
time: 127ms
memory: 58656kb
input:
499993 170472 1 2 1 3 1 4 4 5 5 6 4 7 6 8 5 9 8 10 6 11 6 12 10 13 13 14 11 15 14 16 15 17 14 18 16 19 16 20 17 21 17 22 20 23 19 24 21 25 23 26 22 27 27 28 24 29 24 30 28 31 31 32 30 33 29 34 29 35 35 36 33 37 34 38 36 39 36 40 36 41 41 42 40 43 41 44 39 45 45 46 42 47 47 48 44 49 45 50 46 51 50 52...
output:
65062419628
result:
ok single line: '65062419628'
Test #4:
score: 0
Accepted
time: 99ms
memory: 57828kb
input:
499994 801 1 2 2 3 1 4 2 5 2 6 1 7 7 8 4 9 6 10 10 11 7 12 7 13 10 14 13 15 15 16 14 17 16 18 18 19 15 20 17 21 18 22 19 23 21 24 23 25 21 26 26 27 27 28 24 29 28 30 29 31 27 32 30 33 28 34 29 35 35 36 31 37 36 38 36 39 38 40 36 41 36 42 38 43 38 44 42 45 41 46 41 47 47 48 46 49 45 50 49 51 49 52 48...
output:
285905307
result:
ok single line: '285905307'
Test #5:
score: 0
Accepted
time: 100ms
memory: 57812kb
input:
499990 275 1 2 2 3 2 4 3 5 3 6 4 7 5 8 4 9 4 10 10 11 7 12 9 13 10 14 12 15 13 16 15 17 16 18 18 19 16 20 19 21 20 22 17 23 23 24 22 25 20 26 23 27 22 28 26 29 27 30 27 31 29 32 27 33 33 34 33 35 31 36 31 37 32 38 37 39 35 40 37 41 39 42 37 43 38 44 43 45 42 46 43 47 43 48 47 49 45 50 49 51 47 52 47...
output:
98388719
result:
ok single line: '98388719'
Test #6:
score: 0
Accepted
time: 142ms
memory: 60236kb
input:
499999 419261 1 2 2 3 3 4 2 5 3 6 4 7 2 8 6 9 8 10 10 11 10 12 11 13 13 14 12 15 10 16 16 17 14 18 16 19 17 20 16 21 17 22 17 23 20 24 20 25 22 26 26 27 26 28 27 29 24 30 25 31 27 32 30 33 32 34 29 35 34 36 31 37 37 38 38 39 34 40 40 41 37 42 42 43 43 44 40 45 45 46 42 47 42 48 46 49 46 50 45 51 47 ...
output:
174917393258
result:
ok single line: '174917393258'
Test #7:
score: 0
Accepted
time: 97ms
memory: 57816kb
input:
499999 839 1 2 1 3 3 4 2 5 2 6 4 7 6 8 6 9 7 10 10 11 11 12 10 13 12 14 11 15 14 16 13 17 12 18 18 19 16 20 15 21 16 22 17 23 19 24 24 25 24 26 26 27 23 28 24 29 26 30 28 31 29 32 30 33 28 34 34 35 35 36 31 37 35 38 34 39 36 40 35 41 39 42 42 43 40 44 44 45 40 46 41 47 43 48 44 49 47 50 50 51 47 52 ...
output:
299869724
result:
ok single line: '299869724'
Test #8:
score: 0
Accepted
time: 121ms
memory: 84304kb
input:
499994 469174 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
110061651964
result:
ok single line: '110061651964'
Test #9:
score: 0
Accepted
time: 82ms
memory: 81740kb
input:
499994 688 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 ...
output:
235984
result:
ok single line: '235984'
Test #10:
score: 0
Accepted
time: 99ms
memory: 82664kb
input:
499990 141264 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
9977617584
result:
ok single line: '9977617584'
Test #11:
score: 0
Accepted
time: 122ms
memory: 82788kb
input:
499999 210371 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
22128058078
result:
ok single line: '22128058078'
Test #12:
score: 0
Accepted
time: 350ms
memory: 60820kb
input:
499997 427984 1 2 2 3 1 4 2 5 5 6 5 7 5 8 1 9 3 10 3 11 5 12 7 13 3 14 14 15 10 16 8 17 6 18 1 19 11 20 14 21 9 22 6 23 5 24 8 25 1 26 17 27 20 28 27 29 19 30 18 31 22 32 18 33 4 34 16 35 14 36 6 37 17 38 36 39 33 40 37 41 27 42 21 43 32 44 18 45 27 46 33 47 35 48 2 49 47 50 32 51 48 52 40 53 11 54 ...
output:
213979261810
result:
ok single line: '213979261810'
Test #13:
score: 0
Accepted
time: 2ms
memory: 22812kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 341ms
memory: 61420kb
input:
499990 449066 1 2 2 3 1 4 2 5 4 6 4 7 7 8 6 9 8 10 9 11 5 12 3 13 3 14 3 15 13 16 7 17 13 18 11 19 11 20 18 21 5 22 18 23 10 24 8 25 5 26 22 27 24 28 18 29 5 30 23 31 12 32 19 33 20 34 34 35 16 36 5 37 24 38 10 39 25 40 16 41 18 42 28 43 12 44 28 45 14 46 15 47 34 48 16 49 40 50 3 51 30 52 40 53 8 5...
output:
224515847140
result:
ok single line: '224515847140'
Test #15:
score: 0
Accepted
time: 346ms
memory: 62216kb
input:
499998 296976 1 2 1 3 3 4 1 5 2 6 4 7 7 8 8 9 7 10 1 11 11 12 6 13 4 14 4 15 10 16 2 17 9 18 10 19 1 20 7 21 19 22 7 23 18 24 17 25 7 26 19 27 11 28 12 29 25 30 25 31 9 32 8 33 12 34 22 35 31 36 13 37 12 38 27 39 5 40 29 41 18 42 37 43 25 44 25 45 38 46 4 47 1 48 16 49 34 50 6 51 6 52 22 53 47 54 25...
output:
148478316284
result:
ok single line: '148478316284'
Test #16:
score: 0
Accepted
time: 252ms
memory: 55172kb
input:
499991 620 1 2 2 3 2 4 3 5 3 6 1 7 2 8 5 9 7 10 8 11 11 12 1 13 12 14 10 15 11 16 12 17 10 18 9 19 12 20 17 21 21 22 6 23 17 24 23 25 16 26 10 27 23 28 13 29 11 30 26 31 18 32 6 33 15 34 3 35 32 36 32 37 34 38 17 39 37 40 26 41 24 42 40 43 21 44 34 45 5 46 4 47 21 48 12 49 5 50 11 51 39 52 7 53 31 5...
output:
309963582
result:
ok single line: '309963582'
Test #17:
score: 0
Accepted
time: 359ms
memory: 61704kb
input:
499996 264554 1 2 1 3 3 4 4 5 4 6 4 7 2 8 1 9 8 10 7 11 7 12 1 13 10 14 2 15 3 16 14 17 4 18 5 19 6 20 16 21 8 22 19 23 22 24 20 25 7 26 4 27 26 28 24 29 8 30 15 31 15 32 14 33 25 34 17 35 32 36 1 37 6 38 5 39 11 40 5 41 20 42 21 43 36 44 29 45 32 46 20 47 10 48 29 49 35 50 33 51 48 52 32 53 26 54 3...
output:
132267626666
result:
ok single line: '132267626666'
Test #18:
score: 0
Accepted
time: 101ms
memory: 57800kb
input:
499997 252 1 2 1 3 2 4 2 5 4 6 6 7 6 8 8 9 4 10 7 11 8 12 11 13 8 14 12 15 12 16 11 17 15 18 15 19 16 20 18 21 20 22 21 23 21 24 20 25 23 26 21 27 24 28 26 29 27 30 26 31 31 32 28 33 29 34 29 35 30 36 31 37 35 38 37 39 37 40 35 41 36 42 39 43 39 44 42 45 41 46 44 47 42 48 46 49 46 50 47 51 48 52 47 ...
output:
89992070
result:
ok single line: '89992070'
Test #19:
score: 0
Accepted
time: 103ms
memory: 57752kb
input:
499997 935 1 2 1 3 1 4 2 5 1 6 3 7 3 8 7 9 8 10 10 11 10 12 10 13 9 14 12 15 15 16 16 17 15 18 13 19 14 20 18 21 18 22 17 23 21 24 21 25 21 26 24 27 27 28 25 29 29 30 27 31 29 32 27 33 32 34 33 35 35 36 34 37 37 38 35 39 37 40 37 41 40 42 40 43 43 44 41 45 42 46 43 47 46 48 48 49 47 50 50 51 50 52 4...
output:
334159450
result:
ok single line: '334159450'
Test #20:
score: 0
Accepted
time: 104ms
memory: 57752kb
input:
499994 876 1 2 1 3 1 4 1 5 1 6 5 7 3 8 7 9 6 10 7 11 7 12 8 13 13 14 11 15 12 16 13 17 14 18 16 19 19 20 19 21 19 22 18 23 21 24 19 25 21 26 24 27 26 28 27 29 28 30 28 31 29 32 29 33 33 34 33 35 31 36 33 37 35 38 34 39 36 40 38 41 40 42 41 43 38 44 43 45 42 46 42 47 47 48 45 49 44 50 47 51 51 52 48 ...
output:
312803574
result:
ok single line: '312803574'