【Bzoj3784】树上的路径

Source and Judge

Bzoj3784

Problem

【Description】
给定一个n个结点的树,结点用正整数1..n编号,每条边有一个正整数权值。
用d(a,b)表示从结点a到结点b路边上经过边的权值,输出前大M的距离(去同两个点)。
【Input】
第一行两个正整数N,M
下面N-1行,每行三个正整数a,b,c。
表示结点a到结点b有一条权值为c的边。
【Output】
共M行,如题所述。
【Limited conditions】
a,b<=n,c<=10000
N<=50000
M<=Min(300000,n*(n-1)/2)
【Sample input】
5 10
1 2 1
1 3 2
2 4 3
2 5 4
【Sample output】
7 7 6 5 4 4 3 3 2 1
【Sample explanation】

Record

2h

Analysis

请先思考后再展开

首先,有个弱化版:超级钢琴
那么现在假设你已经理解了上面这道题

然后我们从暴力开始思考,显然枚举每个起点dfs去搞,复杂度是n^2的

然后既然是前m大,当然是用堆维护
尝试枚举起点后,搞出一个dfs序,那么以【数量与深度有关的每个父亲】作为中介,搞出一条条链,而且显然【终点】是连续的。那么因为不能重复,考虑对于点y,只找dfs序比y小的点x。
为了方便,不先枚举起点,而是先枚举中介父亲,然后才是起点。
于是现在每个点被访问的次数是深度,复杂度是深度*n

那么现在大概就能拿到不错的分数了
但是很容易被链啊,扫把啊什么的卡
主要是这个“深度”
所以点分治一波就好啦
然后就是nlogn了

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=51000,MAXID=MAXN*40;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct Nod
{
int hou;
int siz;
bool v;
}p[MAXN];
struct Edge
{
int y,c,g;
}e[MAXN*2];
int ln=0;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,c,p[x].hou};p[x].hou=ln;
e[++ln]=(Edge){x,c,p[y].hou};p[y].hou=ln;
}
int n,k;
//*******************实现*******************
int h[MAXID];//当前dfs序节点与当前中介父亲
int id=0;
void pre(int x,int fa,int dis)
{
h[++id]=dis;
p[x].siz=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa or p[y].v) continue;
pre(y,x,dis+e[k].c);
p[x].siz+=p[y].siz;
}
}
int st[MAXID][20];
int bin[20],lg[MAXID];
int _mx(int x,int y)
{
return (h[x]>h[y])?x:y;
}
void preST()
{
bin[0]=1;for(int i=1;bin[i]<=id;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<=id;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=id;i++) st[i][0]=i;
for(int j=1;bin[j]<=id;j++)
for(int i=1;i+bin[j]-1<=id;i++)
st[i][j]=_mx(st[i][j-1],st[i+bin[j-1]][j-1]);
}
int rmq(int l,int r)
{
int t=lg[r-l+1];
return _mx( st[l][t],st[r-bin[t]+1][t] );
}
int f[MAXN];
int G,sum;
void getrt(int x,int fa)
{
f[x]=0;p[x].siz=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa or p[y].v) continue;
getrt(y,x);
f[x]=mymax(f[x],p[y].siz);
p[x].siz+=p[y].siz;
}
f[x]=mymax(f[x],sum-p[x].siz);
if(f[x]<f[G]) G=x;
}
struct Data
{
int now,l,r;
int mx;
};
vector<Data> tmp;
void divi(int x)
{
p[x].v=1;
int begin=id;
h[++id]=0;//自己
int ss=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(p[y].v) continue;
pre(y,x,e[k].c);
for(int i=1;i<=p[y].siz;i++)
tmp.push_back( (Data){begin+ss+i,begin+1,begin+ss,0} );
ss+=p[y].siz;
}
//注意不能合并循环,因为dfs序要求【同深度同层】,等完成后再分治
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(p[y].v) continue;
sum=p[y].siz;G=0;getrt(y,x);divi(G);
}
}
bool operator < (Data a,Data b)
{
return h[a.now]+h[a.mx]<h[b.now]+h[b.mx];
}
priority_queue<Data> q;
void solve()
{
f[0]=INF;G=0;sum=n;getrt(1,0);divi(G);
preST();
int tz=tmp.size();
for(int i=0;i<tz;i++)
{
tmp[i].mx=rmq(tmp[i].l,tmp[i].r);//debug 忘记st表还没做好
q.push(tmp[i]);
}
while(k--)
{
Data x=q.top();q.pop();
printf("%d\n",h[x.now]+h[x.mx]);
if(x.l<=x.mx-1) q.push( (Data){x.now,x.l,x.mx-1,rmq(x.l,x.mx-1)} );
if(x.mx+1<=x.r) q.push( (Data){x.now,x.mx+1,x.r,rmq(x.mx+1,x.r)} );
}
}
//*******************主函数*******************
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n-1;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
}
solve();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/1486.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%