欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[UESTC SC T1] 最大疯子树

程序员文章站 2022-04-25 15:18:39
...

题面:[UESTC SC T1] 最大疯子树

 

题目描述比较清楚

首先简化情况,考虑仅仅为一条链的情况
那么满足条件的链一定是这样的:

[UESTC SC T1] 最大疯子树

那么这条链的两端一定是大于等于中间的
就形成一个“沟”
接下来我们假设再有一条满足条件的链经过其中一点
[UESTC SC T1] 最大疯子树

那么这样一个东西就可以用一个三维的“坑”或者是“盆”来形象的描述
那么这道题就是从一棵树上选择一个子图,使得这个子图满足两个点之间的路径上的点都小于这两点。

那么这个“盆”怎么去维护呢
有位大佬用   换根法  将这道题O(n)A了
[UESTC SC T1] 最大疯子树
 

 

[UESTC SC T1] 最大疯子树

接下来说说我的做法

对于一个“盆”的结构,我可以直接由“盆”边向“盆”心维护
即从大到小的对于每个节点,维护其所有比他小的能够一次到达的节点。
这样我便能够保证“盆”心能够被所有比它大的“盆”边去维护。
因为是从大到小,所以每个能够作为“盆”边的点或其子节点一定会一次更新到一个“盆”心

    ans[v]+=ans[x]+1
其中v节点的值小于x节点,ans[x]表示以x节点为“盆”心但不包括x节点本身所能形成的最大的满足条件的联通快上的节点的个数

那么最后再枚举一遍所有的点找到ans[x]最大的点的值,再+1进行输出就行了。

就是这样一个过程:

for(int i=1;i<=n;i++)
{
    int x=sa[i].num;
    for(int j=0;j<a[x].size();j++)
	if(del[x]>=del[a[x][j]])
	    ans[a[x][j]]+=(ans[x]+1);
}

其中sa是用来根据点权进行从大到小排序后的数组

想通了之后,便是全代码了:

#include<bits/stdc++.h>
#define MAXN 200010
using namespace std;
vector<int>a[MAXN]; 
struct Nod
{
    int num,val;
}sa[MAXN];
bool operator<(Nod a,Nod b)
{
    return a.val>b.val;
}
int del[MAXN];
int ans[MAXN];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int x,y;
        memset(ans,0,sizeof(ans));
	memset(del,0,sizeof(del));
	for(int i=1;i<=n;i++)
	    a[i].clear();		
        for(int i=1;i<=n;i++)
	{
	    scanf("%d",&sa[i].val);
	    sa[i].num=i;
	    del[i]=sa[i].val;
	}
	sort(sa+1,sa+n+1);
	for(int i=1;i<n;i++)
	{
	    scanf("%d%d",&x,&y);
	    a[x].push_back(y);
	    a[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
	    int x=sa[i].num;
	    for(int j=0;j<a[x].size();j++)
		if(del[x]>=del[a[x][j]])
		    ans[a[x][j]]+=(ans[x]+1);
	}
	int anss=0;
	for(int i=1;i<=n;i++)
	    anss=max(anss,ans[i]+1);
	printf("%d\n",anss);
    }
    return 0;
}

 

相关标签: 排序