社区讨论

AC了但是有一个小小的疑问,求大佬解答

P3304[SDOI2013] 直径参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mhjidajf
此快照首次捕获于
2025/11/04 03:03
4 个月前
此快照最后确认于
2025/11/04 03:03
4 个月前
查看原帖
这是AC代码:
CPP
**#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 5;

int n,dep[N],l,r,f[N],maxx,length[N],ll[N],rr[N],ww[N],a[N],cnt,cnt1,maxdep;
bool vis[N];
vector<pair<int,int> > g[N];

void dfs (int u,int fa) {
	f[u] = fa;
	for (auto e : g[u]) {
		int v = e.first;
		int w = e.second;
		
		if (v == fa) continue;
		
		ww[v] = w;
		
		dep[v] = dep[u] + w;
		dfs (v,u);
	}
	
	if (dep[u] > maxx) {
		maxx = dep[u];
		r = u;
	}
	
}

void dfs1 (int u,int fa) {
	
	for (auto e: g[u]) {
		int v = e.first;
		int w = e.second;
		
		if (v == fa || vis[v] == true) continue;
		
		dep[v] = dep[u] + w;
		
		dfs1 (v,u);
		
	}
	if (dep[u] > maxdep) {
		maxdep = dep[u];
	}
}

signed main () {
	
	cin >> n;
	
	for (int i = 1;i <= n - 1;i ++) {
		int a,b,c;
		cin >> a >> b >> c;
		
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	
	dfs (1,-1);
	l = r;
	dep[r] = 0;
    maxx = 0;
	dfs (r,-1);
	
	vis[l] = vis[r] = true;
	int disl = maxx,disr = 0;
	int id = r;
	cnt = 0;
	
	while (id != l) {
		
		vis[id] = true;
		disl -= ww[id];
		ll[cnt] = disl;
		disr += ww[id];
		rr[cnt] = disr;
		id = f[id];
		a[cnt] = id;
		++ cnt;
		
	}
	
	for (int i = 0;i < cnt;i ++) {
		dep[a[i]] = 0;
		dfs1 (a[i],-1);
		length[a[i]] = maxdep;
		maxdep = 0;
	}
	
	int rend = cnt - 1,lfirst = 0;
	
	for (int i = 0;i < cnt;i ++) {
		if (length[a[i]] == rr[i]) rend = i;
		if (length[a[i]] == ll[i]) {
			lfirst = i;
			break;
		}
	}
	cout << maxx << '\n' <<  lfirst - rend << '\n';
	return 0;
}
这是我的代码:
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 5;

int n,dep[N],l,r,f[N],maxx,length[N],ll[N],rr[N],ww[N],a[N],cnt,cnt1,maxdep;
bool vis[N];
vector<pair<int,int> > g[N];

void dfs (int u,int fa) {
	f[u] = fa;
	for (auto e : g[u]) {
		int v = e.first;
		int w = e.second;
		
		if (v == fa) continue;
		
		ww[v] = w;
		
		dep[v] = dep[u] + w;
		dfs (v,u);
	}
	
	if (dep[u] > maxx) {
		maxx = dep[u];
		r = u;
	}
	
}

void dfs1 (int u,int fa) {
	
	for (auto e: g[u]) {
		int v = e.first;
		int w = e.second;
		
		if (v == fa || vis[v] == true) continue;
		
		dep[v] = dep[u] + w;
		
		dfs1 (v,u);
		
	}
	if (dep[u] > maxdep) {
		maxdep = dep[u];
	}
}

signed main () {
	
	cin >> n;
	
	for (int i = 1;i <= n - 1;i ++) {
		int a,b,c;
		cin >> a >> b >> c;
		
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	
	dfs (1,-1);
	l = r;
	dep[r] = 0;
  //  maxx = 0; 这里没有给maxx清零,然后WA了67两个点,但第二遍dfs求得长度不是一定会比第一遍大于或者等于吗,这样不就更新了吗,为什么要清空啊。
	dfs (r,-1);
	
	vis[l] = vis[r] = true;
	int disl = maxx,disr = 0;
	int id = r;
	cnt = 0;
	
	while (id != l) {
		
		vis[id] = true;
		disl -= ww[id];
		ll[cnt] = disl;
		disr += ww[id];
		rr[cnt] = disr;
		id = f[id];
		a[cnt] = id;
		++ cnt;
		
	}
	
	for (int i = 0;i < cnt;i ++) {
		dep[a[i]] = 0;
		dfs1 (a[i],-1);
		length[a[i]] = maxdep;
		maxdep = 0;
	}
	
	int rend = cnt - 1,lfirst = 0;
	
	for (int i = 0;i < cnt;i ++) {
		if (length[a[i]] == rr[i]) rend = i;
		if (length[a[i]] == ll[i]) {
			lfirst = i;
			break;
		}
	}
	cout << maxx << '\n' <<  lfirst - rend << '\n';
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...