更向天涯

用户名：20110618li

访问量：42268

签　名：

向天涯进发！

等　　级
排　　名	12
经　　验	25711
参赛次数	28
文章发表	502
年　　龄	45
在职情况	在职
学　　校	柏苑中心小学
专　　业	编程

　　自我简介：

无情未必真豪杰，怜子如何不丈夫。

TA的其他文章

2996: 古代密码
浏览：113

你可能喜欢

3144: 蓝桥杯2023年第十四届省赛真题-颜色平衡树

　　作者: 更向天涯　　　　发表时间：2023-05-04 20:17:30 浏览：1546　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-颜色平衡树

```cpp
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N=2e5+1;
int n,m,Son,cnt[N],col[N],siz[N],son[N],sum,res,L[N],R[N],dfn,id[N];
vector<int>G[N];
multiset<int>st;
void dfs1(int x,int f)
{
    L[x]=++dfn;
    id[dfn]=x;
    siz[x]=1;
    for(int y:G[x])
    {
        if(y==f)
            continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(!son[x]||siz[y]>siz[son[x]])
            son[x]=y;
    }
    R[x]=dfn;
    return;
}
void add(int x)
{
    if(cnt[col[x]])
        st.erase(st.find(cnt[col[x]]));
    cnt[col[x]]++;
    st.insert(cnt[col[x]]);
    return;
}
void del(int x)
{
    st.erase(st.find(cnt[col[x]]));
    cnt[col[x]]--;
    if(cnt[col[x]])
        st.insert(cnt[col[x]]);
    return;
}
void dfs2(int x,int f,bool keep)
{
    for(int y:G[x])
    {
        if(y==f||y==son[x])
            continue;
        dfs2(y,x,false);
    }
    if(son[x])
        dfs2(son[x],x,true);
    for(int y:G[x])
    {
        if(y==f||y==son[x])
            continue;
        for(int i=L[y];i<=R[y];i++)
            add(id[i]);
    }
    add(x);
    int mi=*st.begin(),ma=*prev(st.end());
    if(mi==ma)
        res++;
    if(!keep)
        for(int i=L[x];i<=R[x];i++)
            del(id[i]);
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>col[i]>>x;
        G[x].push_back(i);
        G[i].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    cout<<res;
    return 0;
}
```

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

更向天涯

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

小九九（C语言代码）

3144: 蓝桥杯2023年第十四届省赛真题-颜色平衡树

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【偶数求和】（C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

【金明的预算方案】（C++代码）

剪刀石头布（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

星期判断机（C语言代码）

分糖果（C语言代码）

更向天涯

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

小九九 （C语言代码）

3144: 蓝桥杯2023年第十四届省赛真题-颜色平衡树

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【偶数求和】 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

【金明的预算方案】 （C++代码）

剪刀石头布 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

星期判断机 （C语言代码）

分糖果 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

小九九（C语言代码）

　　评论区

【偶数求和】（C语言代码）

【金明的预算方案】（C++代码）

剪刀石头布（C语言代码）

星期判断机（C语言代码）

分糖果（C语言代码）