社区讨论
乱搞过了?
P3174[HAOI2009] 毛毛虫参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo15je5z
- 此快照首次捕获于
- 2023/10/22 15:33 2 年前
- 此快照最后确认于
- 2023/11/02 15:05 2 年前
这题可能需要换根DP,但是我设的状态好像不是很好,不是很好换根。于是我开始乱搞,人类智慧一下发现好像让重心做根会比较优秀,然后用重心做根,跑一次就出来了。
这题 表示从叶子到 最长的毛毛虫,然后 表示在 的子树中经过 的最长毛毛虫。然后取个 就行了。
有无巨验证正确性 || 提供 hack 数据/yiw
这里面用堆存了一些东西,所以时间复杂度大概是 的。
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 条回复,欢迎继续交流。
正在加载回复...