洛谷 P3304 [SDOI2013] 直径 题解

洛谷 P3304 [SDOI2013] 直径 题解

题目链接

题目分析

第一部分好说,求直径,dfs或者DP都可以。

第二部分,有一个定理,就是所有直径中点重叠。

那么有两种情况

  • 一种是中点在一个节点上,那么显然这个点是每条直径的终点,也就是说直径的一半相等。从这个点出发dfs,找出所有最远点。如果只有两条,输出depth之和。否则求lca,lca的depth就是重叠的数量。

  • 另一种,中点在一条边上。从这个边出发,两侧分别dfs找最远,再分类讨论,有的求lca,有的输出。具体见代码即可。

题解中还有其他思路:比如从一条直径上开始dfs(利用直径同侧长度一定相等的性质),还有两次dp求出总cnt和边cnt进行统计的,还有去掉中点所在边之后进行RootLeafPath的。这些思路都很有用。

顺便提一句,在题解里面看到了专门用结构体Data来统计数据(维护最大值和出现次数)以及通过左右分开上升最大值来排除自身这两个trick,觉得十分好用。


代码

#include <bits/stdc++.h>

#define N (long long)(200000 + 5)
#define LOGN (long long)(25)

using namespace std;

typedef long long LL;

struct node
{
	LL v, w, next;
}e[N * 2];

LL n;

LL head[N];
LL cnt;

LL d1[N],d2[N];
LL k1[N],k2[N];
LL d,o;
bool vis[N];//

void adde(int u, int v, int w)
{
	cnt++;
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

void dpdfs(int p)
{
	vis[p] = true;
	d1[p] = d2[p] = 0;
	k1[p] = k2[p] = 0;
	for(int i = head[p];i != 0;i = e[i].next)
	{
		if(!vis[e[i].v])
		{
			vis[e[i].v] = true;
			dpdfs(e[i].v);
			if(d1[e[i].v] + e[i].w > d1[p])
			{
				d2[p] = d1[p];
				k2[p] = k1[p];
				d1[p] = d1[e[i].v] + e[i].w;
				k1[p] = e[i].v;
			}
			else if(d1[e[i].v] + e[i].w > d2[p])//
			{
				d2[p] = d1[e[i].v] + e[i].w;
				k2[p] = e[i].v;
			}
		}
	}
	if(d2[p] + d1[p] > d)
	{
		d = d2[p] + d1[p];
		o = p;
	}
	vis[p] = false;
}

LL depth[N];
LL len[N];
LL maxlendep1;
LL maxlendep2;
LL maxlen1;
LL maxlen2;
LL maxlenidx1[N];
LL maxlenidx2[N];
LL maxlencnt1;
LL maxlencnt2;

void deepdfs(int p,LL *mxi,LL &mxc,LL &mxl, LL &mxd)
{
	vis[p] = true;
	for(int i = head[p];i != 0;i = e[i].next)
	{
		if(!vis[e[i].v])
		{
			vis[e[i].v] = true;
			depth[e[i].v] = depth[p] + 1;
			len[e[i].v] = len[p] + e[i].w;
			if(mxl < len[e[i].v])
			{
				mxl = len[e[i].v];
				mxd = depth[e[i].v];
				mxc = 1;
				mxi[mxc] = e[i].v;
			}
			else if(mxl == len[e[i].v])
			{
				mxi[++mxc] = e[i].v;
			}
			deepdfs(e[i].v,mxi,mxc,mxl,mxd);
		}
	}
	vis[p] = false;
}

int lcadepth[N];
int fa[N][LOGN];

void lcadfs(int p)
{
	vis[p] = true;
	for(int i = head[p];i != 0;i = e[i].next)
	{
		if(!vis[e[i].v])
		{
			vis[e[i].v] = true;
			lcadepth[e[i].v] = lcadepth[p] + 1;
			fa[e[i].v][0] = p;
			for(int j = 1;j <= log2(n);j++)
				fa[e[i].v][j] = fa[fa[e[i].v][j - 1]][j - 1];
			
			lcadfs(e[i].v);
		}
	}
	vis[p] = false;
}

int lca(int x, int y)
{
	if(lcadepth[y] > lcadepth[x])
		swap(x,y);
	for(int i = log2(n); i >= 0;i--)
		if(lcadepth[fa[x][i]] >= lcadepth[y])
		{
			x = fa[x][i];
		}
			
	if(x == y) return x;
	for(int i = log2(n);i >= 0;i--)
		if(fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	return fa[x][0];
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n - 1;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		adde(u,v,w);
		adde(v,u,w);
	}
	dpdfs(1);
	cout << d << "\n";
	LL idx = o, lidx = idx;
	LL deep = 0;
	while(idx != 0)
	{
		if(deep + d2[o] >= d / 2)
		{
			if(((d % 2) == 0) && ((deep + d2[o]) == (d / 2)))
			{
				lidx = idx;
			}
			break;
		}
		lidx = idx;
		idx = k1[idx];
		deep += d1[lidx] - d1[idx];
	}
	
	if(idx != lidx)
	{
		vis[lidx] = true;
		depth[idx] = 0;
		len[idx] = 0;
		deepdfs(idx,maxlenidx1,maxlencnt1,maxlen1,maxlendep1);
		vis[lidx] = false;
		
		
		vis[idx] = true;
		depth[lidx] = 0;
		len[lidx] = 0;
		deepdfs(lidx,maxlenidx2,maxlencnt2,maxlen2,maxlendep2);
		vis[idx] = false;

		lcadepth[0] = -1;
		lcadfs(idx);
		int lca1 = 0, lca2 = 0;
		if(maxlencnt1 >= 1)
		{
			lca1 = maxlenidx1[1];
			for(int i = 2;i <= maxlencnt1;i++)
			{
				lca1 = lca(lca1,maxlenidx1[i]);
			}
		}
		if(maxlencnt2 >= 1)
		{
			lca2 = maxlenidx2[1];
			for(int i = 2;i <= maxlencnt2;i++)
			{
				lca2 = lca(lca2,maxlenidx2[i]);
			}	
		}
		
		
		int cnt1 = maxlencnt1, cnt2 = maxlencnt2;
		
		if(cnt1 == 1 && cnt2 == 0) cout << maxlendep1 + 1 << "\n";
		if(cnt1 == 0 && cnt2 == 1) cout << maxlendep2 + 1 << "\n";
		if(cnt1 == 2 && cnt2 == 0) cout << depth[lca1] + 1 << "\n";
		if(cnt1 == 1 && cnt2 == 1) cout << maxlendep1 + maxlendep2 << "\n";
		if(cnt1 == 0 && cnt2 == 2) cout << depth[lca2] + 1 << "\n";
		if(cnt1 >= 2 && cnt2 == 1) cout << depth[lca1] + maxlendep2 + 1 << "\n";
		if(cnt1 == 1 && cnt2 >= 2) cout << maxlendep1 + depth[lca2] + 1 << "\n";
		if(cnt1 >= 2 && cnt2 >= 2) cout << depth[lca1] + 1 + depth[lca2] << "\n";
	}
	else
	{
		vis[idx] = true;
		depth[idx] = 0;
		len[idx] = 0;
		deepdfs(idx,maxlenidx1,maxlencnt1,maxlen1,maxlendep1);
		vis[idx] = false;
		
		lcadepth[0] = -1;
		lcadfs(idx);
		int lca1 = 0;
		if(maxlencnt1 >= 1)
		{
			lca1 = maxlenidx1[1];
			for(int i = 2;i <= maxlencnt1;i++)
			{
				lca1 = lca(lca1,maxlenidx1[i]);
			}
		}
		
		if(maxlencnt1 == 2) cout << depth[maxlenidx1[1]] + depth[maxlenidx1[2]] << "\n";
		else cout << depth[lca1] << "\n";
		
	}
	return 0;
}
/*
6
3  1 80
1  4 10
4  2 70
4  5 50
4  6 90
*/

/*
6
1 2 1
2 3 4
2 4 3
1 6 2
1 5 3
*/

热门相关:亿万盛宠只为你   不科学御兽   未来兽世:买来的媳妇,不生崽   阿岛前门镇压   我的爱人借给你