P11378 题解

· · 题解

P11378 题解

Step 0 Preface 前言

博客食用更佳 本蒟蒻的第 1 篇题解。场上 30 min秒掉，也是我唯一做出来的一道题，当时交了三次，前两次都得了 2.5 分，第三次我不抱太大信心，但是看着那一抹绿色，我陷入了沉思……另一道题只得了 7.5 分，估完分后发现总分 66.5 ，能过，但不能免普及初赛。

Step 1 Problem+Idea 题意+思路

简单来说求这棵树满足 a_i<a_j 的最大连通分量。

Step 2 Code 代码

用 bfs 只能得 40 分，赛时 bfs 竟然过了，不得不说数据太水了，这是 bfs 的代码:

#include<bits/stdc++.h>
#define llmax numeric_limits<long long>::max()
#define llmin numeric_limits<long long>::min()
#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define pb push_back
#define gc getchar
#define pc putchar
#define ps puts
#define nl ps("")
#define chkup(ch) ch>='A'&&ch<='Z'
#define chklow(ch) ch>='a'&&ch<='z'             //请忽略我的火车头 
using namespace std;
const int N=1e5+10;
int a[N], ans;
vector<int> g[N];
bool vis[N];
bool chk(int x, int s) {              //x 代表当前遍历到的这个点，s 代表它的上一个点。 
    return !vis[x]&&a[x]<a[s];        //检查是否能入队。 
}
void bfs(int s) {
    int cnt=0;                                   //用来统计连通块大小 
    queue<int> q;
    q.push(s);
    vis[s]=true;
    while(!q.empty()) {
        int x=q.front();                       //1.获取队首元素 
        q.pop();                                 //2.出队
        cnt++;                                   //找到一个点就让连通块大小加1 
        for(int i = 0;i<g[x].size();i++) {       //3.模拟扩展 
            if(chk(g[x][i], x)) {
                q.push(g[x][i]);
                vis[g[x][i]]=true;
            }
        }
    }
    ans=max(ans, cnt);    //将连通块大小与答案相比较
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1;i<=n;i++) {
        scanf("%d", a+i);
    }
    for(int i = 1;i<n;i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].pb(v);                       //建边 
        g[v].pb(u);
    }
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=n;j++) {
            vis[j]=false;
        }
        bfs(i);                       //所有点开始bfs
    }
    printf("%d", ans);                    //输出答案
    return 0;
}

40 pts record\ 那么开始思考正解，用 bfs 可能效率不会太高，可以用 2 个 dfs 来解答:\ 首先第 1 个 dfs 用来求从每个节点开始的满足 a_i<a_j 的数量:

void dfs1(int x, int f) {
    tmp[x]=1;                                   //将初始值设为1 
    for(int i = 0;i<a[x].size();i++) {
        if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环 
            dfs1(a[x][i], x);                   //遍历下一个节点 
            if(w[a[x][i]]<w[x]) {
                tmp[x]+=tmp[a[x][i]];           //如果满足条件，则把子树的数量加给这个点的数量 
            }
        }
    }
}

然后第 2 个 dfs 用来求答案:

void dfs2(int x, int f) {
    if(w[x]>w[f]) {                             //如果满足就将父节点的大小和答案增加给当前节点的答案，因为从当前节点开始会比从父节点开始会多 
        ans[x]+=ans[f]+tmp[f];
    }
    for(int i = 0;i<a[x].size();i++) {
        if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环
            dfs2(a[x][i], x);                   //遍历下一个节点
        }
    }
}

每个 dfs 可以从任意节点开始。\ 完整代码:

#include<bits/stdc++.h>
#define llmax numeric_limits<long long>::max()
#define llmin numeric_limits<long long>::min()
#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define pb push_back
#define gc getchar
#define pc putchar
#define ps puts
#define nl ps("")
#define chkup(ch) ch>='A'&&ch<='Z'
#define chklow(ch) ch>='a'&&ch<='z'             //请忽略我的火车头 
using namespace std;
const int N=1e5+10;
int w[N], tmp[N], ans[N], out;
vector<int> a[N];
void dfs1(int x, int f) {
    tmp[x]=1;                                   //将初始值设为1 
    for(int i = 0;i<a[x].size();i++) {
        if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环 
            dfs1(a[x][i], x);                   //遍历下一个节点 
            if(w[a[x][i]]<w[x]) {
                tmp[x]+=tmp[a[x][i]];           //如果满足条件，则把子树的数量加给这个点的数量 
            }
        }
    }
}
void dfs2(int x, int f) {
    if(w[x]>w[f]) {                             //如果满足就将父节点的大小和答案增加给当前节点的答案，因为从当前节点开始会比从父节点开始会多 
        ans[x]+=ans[f]+tmp[f];
    }
    for(int i = 0;i<a[x].size();i++) {
        if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环
            dfs2(a[x][i], x);                   //遍历下一个节点
        }
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1;i<=n;i++) {
        scanf("%d", w+i);
    }
    for(int i = 1;i<n;i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u].pb(v);                 //建边 
        a[v].pb(u);
    }
    dfs1(1, 0);                     //从1开始，1的父节点是0 
    dfs2(1, 0);
    for(int i = 1;i<=n;i++) {
        ans[i]+=tmp[i];             //最终答案为大小和答案相加的和 
    }
    for(int i = 1;i<=n;i++) {
        out=max(out, ans[i]);       //比大小 
    }
    printf("%d", out);
    return 0;
}

100 pts record