专栏文章

题解：CF1252F Regular Forestation

llinjinkun
CF1252F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9142w
此快照首次捕获于
2025/12/02 15:20
3 个月前
此快照最后确认于
2025/12/02 15:20
3 个月前
查看原文
这真的是紫？撑死蓝吧，而且数据范围那么小，暴力都能过……

Solution 1

由于数据范围过于神秘……
3≤N≤40003 \le N \le 4000
？？？？出题人你善也不能善到这个程度吧……
所以……暴力枚举删哪个点，然后给删除后的所有树跑一遍树哈希求出哈希值判断是否全部一样即可。
时间复杂度 O(N2)O(N^2)。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 4e3+5;
vector<int>e[N];
int h[N];
mt19937 r(time(0));
int rr = r();
int s(int x)
{
    x^=rr;
    x^=(x<<13);
    x^=(x>>7);
    x^=(x<<17);
    x^=rr;
    return x;
}
int root;
int vis[N];
int dfs(int x,int fa)
{
    h[x] = 1;
    for(int v:e[x])
    {
        if(v!=fa&&v!=root)
        {
            vis[v] = 1;
            h[x]+=s(dfs(v,x));
        }
    }
    return h[x];
}
void huan(int x,int v)
{
    h[x]-=s(h[v]);
    h[v]+=s(h[x]);
}
int ans;
void dfs1(int x,int fa)
{
    ans+=h[x];
    for(int v:e[x])
    {
        if(v!=fa&&v!=root)
        {
            vis[v] = 1;
            huan(x,v);
            dfs1(v,x);
            huan(v,x);
        }
    }
}
signed main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i<n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int maxx = -1;
    for(int i = 1;i<=n;i++)
    {
        root = i;
        for(int j = 1;j<=n;j++)
        {
            if(j == i)
            {
                continue;
            }
            if(vis[j] == 0)
            {
                vis[j] = 1;
                dfs(j,0);
            }
        }
        memset(vis,0,sizeof(vis));
        set<int>ss;
        for(int j = 1;j<=n;j++)
        {
            if(j == i)
            {
                continue;
            }
            if(vis[j] == 0)
            {
                ans = 0;
                vis[j] = 1;
                dfs1(j,0);
                ss.insert(ans);
            }
        }
        memset(vis,0,sizeof(vis));
        if(ss.size() == 1&&e[i].size()>1)
        {
            maxx = max(maxx,(int)e[i].size());
        }
    }
    printf("%d",maxx);
    return 0;
}

Solution 2

上面的做法完全是因为出题人太善才能通过的，这里我们将优化上面的做法使其时间复杂度变成 O(N)O(N)。
首先，你要知道，如果删掉一个点之后所有树同构那么这个点一定是树的重心。
为什么？
因为删掉这个点之后所有树同构说明所有树的大小被均分，这不就是满足了树的重心的定义吗？
所以，只需要找到这棵树的所有重心，判断即可。
因为树的重心最多两个，所以时间复杂度舍去没用的常数，就是 O(N)O(N)。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 4e3+5;
vector<int>e[N];
int h[N];
mt19937 r(time(0));
int rr = r();
int sh(int x)
{
    x^=rr;
    x^=(x<<13);
    x^=(x>>7);
    x^=(x<<17);
    x^=rr;
    return x;
}
int root;
int vis[N];
int dfs(int x,int fa)
{
    h[x] = 1;
    for(int v:e[x])
    {
        if(v!=fa&&v!=root)
        {
            vis[v] = 1;
            h[x]+=sh(dfs(v,x));
        }
    }
    return h[x];
}
void huan(int x,int v)
{
    h[x]-=sh(h[v]);
    h[v]+=sh(h[x]);
}
int ans;
void dfs1(int x,int fa)
{
    ans+=h[x];
    for(int v:e[x])
    {
        if(v!=fa&&v!=root)
        {
            vis[v] = 1;
            huan(x,v);
            dfs1(v,x);
            huan(v,x);
        }
    }
}
int minn = 1e9,minnn = 0;
int maxx[N];
int s[N];
int n;
void dfs2(int x,int fa)//求树的重心（这可能只是其中一个）
{
	s[x] = 1;//初始化
	maxx[x] = 0;//找最大子树的变量
	for(int v:e[x])
	{
		if(v!=fa)
		{
			dfs2(v,x);
			s[x]+=s[v];//加上儿子子树的大小
			maxx[x] = max(maxx[x],s[v]);//找到最大的子树
		}
	}
	maxx[x] = max(maxx[x],n-s[x]);//别忘了还有父亲
	if(maxx[x]<minn)//如果比当前的最小值还要小
	{
		minn = maxx[x];//记录最小值
		minnn = x;//记录重心
	}
}
signed main()
{
    scanf("%d",&n);
    for(int i = 1;i<n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs2(1,0);
    int anss[3],cnt = 1;
    anss[1] = minnn;
    for(int v:e[minnn])
    {
        if(maxx[v] == minn)
        {
            anss[++cnt] = v;
            break;
        }
    }
    int maxx = -1;
    for(int i = 1;i<=cnt;i++)
    {
        root = anss[i];
        for(int j = 1;j<=n;j++)
        {
            if(j == root)
            {
                continue;
            }
            if(vis[j] == 0)
            {
                vis[j] = 1;
                dfs(j,0);
            }
        }
        memset(vis,0,sizeof(vis));
        set<int>ss;
        for(int j = 1;j<=n;j++)
        {
            if(j == root)
            {
                continue;
            }
            if(vis[j] == 0)
            {
                ans = 0;
                vis[j] = 1;
                dfs1(j,0);
                ss.insert(ans);
            }
        }
        memset(vis,0,sizeof(vis));
        if(ss.size() == 1&&e[root].size()>1)
        {
            maxx = max(maxx,(int)e[root].size());
        }
    }
    printf("%d",maxx);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...