【Bzoj3124】【Luogu3304】直径

Source and Judge

Sdoi2013
Bzoj3124
Luogu3304

Problem

【Description】
给定一棵树,求直径的长度,以及有多少条边满足【所有的直径都经过】。
【Input】
第一行包含一个整数N,表示节点数。
接下来N-1行,每行三个整数a, b, c ,表示点 a和点b之间有一条长度为c的无向边。
【Output】
共两行。第一行一个整数,表示直径的长度。
第二行一个整数,表示被所有直径经过的边的数量。
【Limited conditions】
2<=N<=200000,所有点的编号都在1..N的范围内,边的权值<=10^9
【Sample input】
6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100
【Sample output】
1110
2
【Sample explanation】
直径共有两条,3 到2的路径和3到6的路径。这两条直径都经过边(3, 1)和边(1, 4)。

Record

30min

Analysis

请先思考

很有趣的一道题
思路来自akc大爷:

  1. 找出一条直径
  2. 把直径扯直,其它子树挂在上面,此时答案一定从其中产生
  3. 预处理出直径上前缀和、后缀和,以及每个子树的最大深度mxi
  4. 从右往左找到第一个满足【mx+sum=L(直径长度)】,则意味着排除左边所有边,记录此l
  5. 从左往右同理,记录r

于是我们就可以枚举左右端点去枚举这种情况:【mx1+sum+mx2=L】
复杂度O(n)

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
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
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=210000;
//*******************全局定义*******************
struct Nod
{
int hou;
int fa;
ll dis;
bool v;
Nod()
{
hou=v=0;
}
}p[MAXN];
struct Edge
{
int y,g;ll c;
}e[MAXN*2];
int ln=0;
void ins()
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
e[++ln]=(Edge){y,p[x].hou,c};p[x].hou=ln;
e[++ln]=(Edge){x,p[y].hou,c};p[y].hou=ln;
}
//*******************实现*******************
int tmp;
void dfs(int x,int fa)
{
p[x].fa=fa;
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;
p[y].dis=p[x].dis+e[k].c;
if(p[y].dis>p[tmp].dis) tmp=y;
dfs(y,x);
}
}
//*******************主函数*******************
int f[MAXN];
int sum[MAXN],mx[MAXN];
int cnt=0;//记录直径
int main()
{
//freopen("tmp.in","r",stdin);
int n;scanf("%d",&n);
for(int i=1;i<=n-1;i++) ins();
tmp=1;p[tmp].dis=0;dfs(tmp,0);int aa=tmp;
tmp=aa;p[tmp].dis=0;dfs(tmp,0);int bb=tmp;
printf("%lld\n",p[bb].dis);
int x=bb;
while(1)
{
f[++cnt]=x;
p[x].v=1;
if(x==aa) break;
x=p[x].fa;
}
for(int i=1;i<=cnt;i++)
{
tmp=f[i];
sum[i]=p[tmp].dis;
p[tmp].dis=0;
dfs(tmp,0);
mx[i]=p[tmp].dis;
}
int l=1;for(int i=cnt;i>=1;i--) if(mx[i]==sum[1]-sum[i]) {l=i;break;}
int r=cnt;for(int i=1;i<=cnt;i++) if(mx[i]==sum[i]) {r=i;break;}
printf("%d",r-l);
}

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

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