BZOJ 3124 直径

发表于 | 更新于

Link

Solution

多条直径相交的形态一定是 类似树网的核，求出直径之后，从直径的一端开始走。记一个点pp到直径左、右端点的距离为dlp,drpdl_p,dr_p,设当前走到的边的左右两点分别为pl,prp_l,p_r，如果从plp_l不走直径的边能走出一条长度为drpldr_{p_l}的路径，或者prp_r能走出dlprdl_{p_r}那这个边就不是直径的公共边。 走到第一条公共边开始累加答案，到第一条非公共边break，就可以解出来了。

Tips

树的直径的性质分析用到了很多反证法。有些结论正向思考无法下手，不妨试试能不能把自己举出的反例否掉，以尝试得出反证的思路。

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=2e5+10;
using std::reverse;
typedef long long LL;
struct Edge{int to,pre,v;}e[MAXN<<1];int id[MAXN],ec=1,n;
void Adde(int f,int t,int v)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;e[ec].v=v;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;e[ec].v=v;
}
int trd[MAXN],pree[MAXN],us[MAXN],ut,dct;
LL d[MAXN],dlen[MAXN],mxd[MAXN],dpf[MAXN],dsf[MAXN];
int BFS(int s)
{
	static int Q[MAXN],he,ta,res;
	Q[he=ta=1]=s;us[s]=ut;d[s]=0,res=s,pree[s]=0;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(us[u]!=ut)
			{
				us[u]=ut;
				d[u]=d[cur]+e[i].v;
				pree[u]=i;
				if(d[u]>d[res]) res=u;
				Q[++ta]=u;
			}
		}
	}
	return res;
}
void getd()
{
	++ut;int st=BFS(1);
	++ut;int nd=BFS(st);
	++ut;
	for(int i=pree[nd];i;i=pree[e[i^1].to])
	{
		trd[++dct]=e[i].to;
		dlen[dct]=e[i].v;
		us[trd[dct]]=ut;
	}
	reverse(trd+1,trd+1+dct);
	reverse(dlen+1,dlen+1+dct);
	for(int i=1;i<=dct;i++)
	{
		mxd[i]=d[BFS(trd[i])];
		dpf[i]=dpf[i-1]+dlen[i];
	}
	for(int i=dct;i;i--) dsf[i]=dsf[i+1]+dlen[i+1];
}
int main()
{
	get(n);
    for(int i=1;i<=n-1;i++)
    {
		int a,b,c;get(a),get(b),get(c);
		Adde(a,b,c);
    }
	getd();
	int ANS=0,p;LL mind;
	for(p=2;p<=dct;p++)
	{
		if(dpf[p]!=mxd[p] && dsf[p-1]!=mxd[p-1])	
			break;
	}
	for(;p<=dct;p++)
	{
		if(dpf[p]==mxd[p] || dsf[p-1]==mxd[p-1]) break;
		else ANS++;
	}
	printf("%lld\n%d\n",dpf[dct],ANS);
	return 0;
}
/* AC Record(Bugs) *
 * WA 多了1？什么情况 [BFS()]..naive
 * * * * * * * * * */