hdu2196 Computer 题解

Jennifer ·

更新时间:2024-09-21

· 612 次阅读

博客园同步

原题链接

简要题意：

多组数据。每组数据给定一棵树，求离每个节点最远的节点的距离。

显然 n≤104n \leq 10^4n≤104 不能用 O(n2)O(n^2)O(n2) 的爆搜解决。我们考虑优化。

在求树的直径时，我们深搜的做法是：

从任意的节点出发找到最远的节点 xxx，xxx 作为直径一端。

从 xxx 节点出发找到最远的节点 yyy，x→yx \rightarrow yx→y 即为直径，yyy 作为直径另一端。

“任意节点” 即保证：

离一个节点最远的点，只会是直径的两个端点。

那么，我们只需要求出直径的两个端点到每个点的距离，然后 max\text{max}max 即可。

时间复杂度：O(n)O(n)O(n).

实际得分：100pts100pts100pts.

细节：注意初始化！

#pragma GCC optimize(2)
#include
using namespace std;
const int N=1e5+1;
inline int read(){char ch=getchar(); int f=1;while(ch'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int dis1[N],n,dis2[N];
//dis1[i] 为 i 到直径一个端点的距离
//dis2[i] 即另一个端点
vector<pair > G[N];
bool h[N];
int maxi=0,maxh;
int mmaxi=0,mmaxh;
inline void dfs1(int dep,int far) {
	if(h[dep]) return ;
	h[dep]=1; if(far>maxi) maxi=far,maxh=dep;
	for(int i=0;immaxi) mmaxi=far,mmaxh=dep;
	dis1[dep]=far;
	for(int i=0;i<G[dep].size();i++) dfs2(G[dep][i].first,far+G[dep][i].second);
}
inline void dfs3(int dep,int far) {
	if(h[dep]) return ;
	h[dep]=1; dis2[dep]=far;
	for(int i=0;i<G[dep].size();i++) dfs3(G[dep][i].first,far+G[dep][i].second);
}
int main() {
	int n; while(scanf("%d",&n)!=EOF) {
		for(int i=2;i<=n;i++) {
			int u=read(),v=read();
			G[u].push_back(make_pair(i,v));
			G[i].push_back(make_pair(u,v)); 
		} memset(h,0,sizeof(h)); dfs1(1,0); // 找到直径一端
		memset(h,0,sizeof(h)); dfs2(maxh,0); // 以 maxh 为一端找另一端
		memset(h,0,sizeof(h)); dfs3(mmaxh,0); // 求另一端的答案
//		printf("%d %d\n",maxh,mmaxh);
//		for(int i=1;i<=n;i++) printf("%d %d\n",dis1[i],dis2[i]),
		for(int i=1;i<=n;i++) printf("%d\n",max(dis1[i],dis2[i])),
		G[i].erase(G[i].begin(),G[i].end());
		memset(dis1,0,sizeof(dis1)); memset(dis2,0,sizeof(dis2));
		maxi=mmaxi=maxh=mmaxh=0; //最后还原数据
	}
	return 0;
}