社区讨论

乱搞过了?

P3174[HAOI2009] 毛毛虫参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lo15je5z
此快照首次捕获于
2023/10/22 15:33
2 年前
此快照最后确认于
2023/11/02 15:05
2 年前
查看原帖
这题可能需要换根DP,但是我设的状态好像不是很好,不是很好换根。于是我开始乱搞,人类智慧一下发现好像让重心做根会比较优秀,然后用重心做根,跑一次就出来了。
这题 fxf_x 表示从叶子到 xx 最长的毛毛虫,然后 ansxans_x 表示在 xx 的子树中经过 xx 的最长毛毛虫。然后取个 max\max 就行了。
有无巨验证正确性 || 提供 hack 数据/yiw
这里面用堆存了一些东西,所以时间复杂度大概是 O(nlogn)O(n\log n) 的。
CPP
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 3e5 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}

int n,m,u,v,maxsize,root,sum;
int f[N],ans[N],son[N],siz[N];
struct node{
	int id,val;
	bool operator < (const node &x) const { return val < x.val; }
};
priority_queue <node> q[N];
vector <int> G[N];


il int read()
{
	int f=0,s=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
	for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
	return f ? -s : s;
}

il void GetRoot(int x,int fa)
{
	siz[x] = 1;
	int s = 0;
	for(re auto y : G[x])
	{
		if(y == fa) continue;
		GetRoot(y,x);
		siz[x] += siz[y];
		s = max(s,siz[y]);
	}
	s = max(s,sum-siz[x]);
	if(s < maxsize) root = x , maxsize = s;
}

il void dfs(int x,int fa)
{
	for(re auto y : G[x])
	{
		if(y == fa) continue;
		dfs(y,x);
		son[x]++;
	}
	for(re auto y : G[x])
	{
		if(y == fa) continue;
		q[x].push({y,f[y]});
		f[x] = max(f[x],f[y]);
	}
	f[x] += son[x];
	if(!son[x]) f[x] = 1 , ans[x] = 1;
	else if(son[x] == 1) ans[x] = q[x].top().val + 1;
	else if(son[x] >= 2)
	{
		auto tmp = q[x].top(); q[x].pop();
		ans[x] = tmp.val + q[x].top().val + son[x] - 1;
		q[x].push(tmp);
	}
}

signed main()
{
	n = maxsize = sum = read() , m = read();
	for(re int i=1;i<=m;i++)
	{
		u = read() , v = read();
		G[u].emplace_back(v) , G[v].emplace_back(u);
	}
	GetRoot(1,0);
	dfs(root,0);
	int Max = 0;
	for(re int i=1;i<=n;i++) Max = max(Max,ans[i]);
	cout << Max;
	return 0;
}

回复

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

正在加载回复...