关于max函数

以下是一段找树的重心的代码：

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 2e5 + 10;
int n;
int Tsiz, siz[maxn], wei[maxn];
vector<pair<int,int> > edg[maxn];
int rt;
bool book[maxn];
inline int _max(int x,int y){return x > y ? x : y;}
void getroot(int u,int f){
    siz[u] = 1;wei[u] = 0;
    // cerr << "u = " << u <<  " f = " << f << endl;
    for(auto i : edg[u]){
        int v = i.first, w = i.second;
        // cerr << "v = " << v << endl;
        if(v != f && !book[v]){
            getroot(v, u);
            siz[u] += siz[v];
            wei[u] = max(wei[u],siz[v]);
        }
    }
    wei[u] = _max(wei[u],Tsiz - siz[u]);
    if(wei[rt] > wei[u])rt = u;
}
signed main(){
    n = read();int u, v, w;
    for(int i = 1;i < n;i++){
        u = read(); v = read(); w = read();
        edg[u].push_back(make_pair(v, w));
        edg[v].push_back(make_pair(u, w));
    }
    Tsiz = n;
    getroot(1, 0);
    return 0;
}

其中使用了自定义的 _max 函数。

而将上面的 _max 替换成 std::max 之后，代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 2e5 + 10;
int n;
int Tsiz, siz[maxn], wei[maxn];
vector<pair<int,int> > edg[maxn];
int rt;
bool book[maxn];
inline int _max(int x,int y){return x > y ? x : y;}
void getroot(int u,int f){
    siz[u] = 1;wei[u] = 0;
    // cerr << "u = " << u <<  " f = " << f << endl;
    for(auto i : edg[u]){
        int v = i.first, w = i.second;
        // cerr << "v = " << v << endl;
        if(v != f && !book[v]){
            getroot(v, u);
            siz[u] += siz[v];
            wei[u] = max(wei[u],siz[v]);
        }
    }
    wei[u] = max(wei[u],Tsiz - siz[u]);
    if(wei[rt] > wei[u])rt = u;
}
signed main(){
    n = read();int u, v, w;
    for(int i = 1;i < n;i++){
        u = read(); v = read(); w = read();
        edg[u].push_back(make_pair(v, w));
        edg[v].push_back(make_pair(u, w));
    }
    Tsiz = n;
    getroot(1, 0);
    return 0;
}

两份代码的唯一差别就是max函数是否手写。

现在假设我们有一个退化成链的树（有边权）（点数为

2\times 10^4

）作为输入数据。

使用命令：-O2 -std=c++14 -fsanitize=address,undefined ，在 WSL 环境下进行编译。

对两份代码使用同样的命令进行编译。

在这份数据下，第一份代码可以正常运行，而第二份代码会出现以下的报错：

CPP

SUMMARY: AddressSanitizer: stack-overflow (/mnt/d/desktop/Desktop/Call_me_Eric/Call_me_Eric-s-Codes/YbtOJ-金牌导航/点分治/B+0xbea6) in getroot(int, int)

但是如果去掉 -O2 命令又可以正常运行了。

现在推测是哪里出现UB行为但是没找到。

向各位谷友求助QAQ

讨论操作

回复

相关推荐

关于max函数