QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #951372 | #2065. Cyclic Distance | xiaopangfeiyu | WA | 36ms | 44280kb | C++14 | 4.7kb | 2025-03-26 09:35:11 | 2025-03-26 09:35:12 |
Judging History
answer
/*
st::
ed::
_/ _/
_/ _/
_/ _/
_/ _/
_/ _/ _/
_/_/_/_/ _/ _/_/_/_/ _/
_/_/_/_/ _/ _/ _/ _/ _/_/ _/_/_/_/_/ _/ _/ _/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/_/_/ _/ _/ _/ _/ _/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/
_/
_/
_/
_/
_/
_/
*/
#include <bits/stdc++.h>
#define i64 long long
#define pii pair<int,int>
const int REN=400000,MAXN=REN+5;
using namespace std;
int n,k;
struct node
{
priority_queue<int,vector<int>,greater<int>>h1,h2;
int v=-1,tag1=0,tag2=0;
int siz() {return h1.size()+h2.size()+(v!=-1);}
void init() {tag1=tag2=0;v=-1;while(h1.size()) {h1.pop();} while(h2.size()) {h2.pop();}}
void add(int x)
{
if(h1.size()<k/2) {h1.push(x-tag1);}
if(x>h1.top()+tag1)
{
int y=h1.top()+tag1;
h1.pop();h1.push(x-tag1);
add(y);
return ;
}
if((k&1)&&v==-1) {v=x;return ;}
if((k&1)&&x>v) {swap(v,x);add(x);return ;}
if(h2.size()<k/2) {h2.push(x-tag2);return ;}
if(x>h2.top()+tag2) {h2.pop();h2.push(x-tag2);return ;}
}
}heap[MAXN];
vector<pii>g[MAXN];
void merge(int x,int y)
{
if(heap[x].siz()<heap[y].siz()) {swap(heap[x],heap[y]);}
while(heap[y].h1.size()) {heap[x].add(heap[y].h1.top()+heap[y].tag1);heap[y].h1.pop();}
while(heap[y].h2.size()) {heap[x].add(heap[y].h2.top()+heap[y].tag2);heap[y].h2.pop();}
if(~heap[y].v) {heap[x].add(heap[y].v);heap[y].v=-1;}
}
void dfs(int x,int fa)
{
heap[x].add(0);
for(auto [v,w]:g[x])
{
if(v==fa) {continue;}
dfs(v,x);
heap[v].tag1+=w<<1;
heap[v].tag2-=w<<1;
merge(x,v);
}
}
void solve()
{
int i;
cin>>n>>k;
for(i=1;i<=n;i++) {heap[i].init();g[i].clear();}
for(i=1;i<n;i++)
{
int x,y,w;
cin>>x>>y>>w;
g[x].emplace_back(y,w);
g[y].emplace_back(x,w);
}
dfs(1,0);
int ans=0;
while(heap[1].h1.size()) {ans+=heap[1].h1.top();heap[1].h1.pop();}
while(heap[1].h2.size()) {ans+=heap[1].h2.top();heap[1].h2.pop();}
if(heap[1].v!=-1&&(k&1)) {ans+=heap[1].v;}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// time_t st=clock();
int i,j,k;
int _;cin>>_;
while(_--) {solve();}
// time_t ed=clock();
// double ret=double(ed-st)/CLOCKS_PER_SEC;
// cerr<<endl<<ret<<'s';
return 0;
}
/*
_/ _/
_/ _/
_/ _/
_/ _/
_/ _/ _/
_/ _/_/_/ _/ _/ _/_/_/ _/
_/_/_/_/_/ _/_/ _/ _/ _/ _/_/_/ _/_/_/_/_/ _/_/ _/ _/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/_/_/_/ _/ _/ _/ _/ _/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/
_/
_/
_/
_/
_/
_/
*/
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 44280kb
input:
1 5 3 1 2 4 1 3 1 1 4 8 4 5 9
output:
44
result:
ok single line: '44'
Test #2:
score: -100
Wrong Answer
time: 36ms
memory: 44280kb
input:
57206 3 2 1 2 574927 2 3 406566 2 2 1 2 308806 4 3 1 2 312588 2 3 500141 2 4 53602 3 3 1 2 797183 2 3 944061 5 3 1 2 624010 2 3 488613 3 4 734514 4 5 497493 5 4 1 2 540278 2 3 488655 2 4 228989 2 5 653896 2 2 1 2 569117 4 2 1 2 821764 2 3 499471 1 4 549060 2 2 1 2 991159 2 2 1 2 482941 5 4 1 2 30462...
output:
1962986 617612 1732662 3482488 4689260 4446214 1138234 3740590 1982318 965882 3578080 5026562 1623414 1885106 1952142 4012796 1691896 3102076 2380932 3076270 6829864 8351820 879020 2500212 3613854 1358950 1182198 2273662 2331560 1681964 11064308 2373066 3163042 3104226 3642898 4693290 6072892 366918...
result:
wrong answer 6th lines differ - expected: '3823636', found: '4446214'