c++程序进行O2优化导致RE的疑问

题意

给出一个由 $n$ 个点，$m$ 条边组成的森林，有 $q$ 组询问,每次询问有以下两种情况

输入 $op = 1$ 时：给出点 $x$，输出点 $x$ 所在的树的直径。
输入 $op = 2$ 时：给出点 $x,y$，（如果 $x,y$ 在同一棵树中则忽略此操作）选择任意两点 $u,v$，使得 $u 跟 $x$ 在同一棵树中且 $v$ 跟 $y$ 在同一棵树中。将 $u,v$ 之间连一条边，使得连边后的到的新树的直径最小。

我写的代码，不加O2优化在洛谷，codeforces都能正确，但是加了O2优化10分：
评测链接

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fat[600005];
int find(int x) {
    return fat[x] == x?x:fat[x] = find(fat[x]);
}
int head[600005],nex[1200005],to[1200005],cnt;
int add(int x,int y) {
    nex[++cnt] = head[x];
    head[x] = cnt;
    to[cnt] = y;
}
int n,m,q; 
bool v[600005];
int maxx,ed1,ed2,root;
int deepest[600005],deepest2[600005];
void find_edge1(int now,int fa,int deep) {
    for(int i = head[now];i;i = nex[i]) {
        if(to[i] != fa) find_edge1(to[i],now,deep + 1);
    }
    if(deep >= maxx) {
        maxx = deep;
        ed1 = now;
    }
    return;
}
void find_edge2(int now,int fa,int deep) {
    for(int i = head[now];i;i = nex[i]) {
        if(to[i] != fa) find_edge2(to[i],now,deep + 1);
    }
    if(deep >= maxx) {
        maxx = deep;
        ed2 = now;
    }
    return;
}
void find_root(int now,int fa,int deep) {
    if(now == ed2) {
        v[now] = 1;
    }
    for(int i = head[now];i;i = nex[i]) {
        if(to[i] != fa) {
            find_root(to[i],now,deep + 1);
            if(v[to[i]]) v[now] = 1;
        }
    }
    if(v[now] and deep == maxx / 2) {
        root = now;
        deepest[root] = maxx - deep;
        deepest2[root] = maxx / 2;
    }
}
void biaoji(int now,int fa) {
    for(int i = head[now];i;i = nex[i]) {
        if(to[i] != fa) biaoji(to[i],now);
    }
    v[now] = 1;
    fat[now] = root;
}
signed main() {
    scanf("%lld %lld %lld",&n,&m,&q);
    for(int i = 1;i <= n;i++) fat[i] = i;
    while(m--) {
        int x,y;
        scanf("%lld %lld",&x,&y);
        add(x,y),add(y,x);
    }
    for(int i = 1;i <= n;i++) {
        if(!v[i]) {
            maxx = 0;
            find_edge1(i,i,0);
            maxx = 0;
            find_edge2(ed1,ed1,0);
            find_root(ed1,ed1,0);
            biaoji(ed1,ed1);
        //    printf("%lld %lld %lld\n",ed1,ed2,root);
        }
    }
    for(int i = 1;i <= q;i++) {
        int op,x,y;
        scanf("%lld",&op);
        if(op == 1) {
            scanf("%lld",&x);
            printf("%lld\n",deepest[find(x)] + deepest2[find(x)]);
        }
        if(op == 2) {
            scanf("%lld %lld",&x,&y);
            x = find(x),y = find(y);
            if(x == y) continue;
            //printf("%lld %lld\n",deepest[x],deepest[y]);
            if(deepest[x] == deepest[y]) {
                fat[y] = x;
                deepest[x]++;
                deepest2[x] = deepest[y];
            }
            else if(deepest[x] > deepest[y]) {
                fat[y] = x;
                if(deepest2[x] < deepest[y] + 1) deepest2[x] = deepest[y] + 1;
            }
            else {
                fat[x] = y;
                if(deepest2[y] < deepest[x] + 1) deepest2[y] = deepest[x] + 1;
            }
        }
    }
    return 0;
}

写回答
好问题 0 提建议
追加酬金
关注问题
分享
邀请回答
编辑收藏删除
收藏举报

1条回答默认最新

清水白石008 2024-08-14 06:53

关注

🕒上午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：人必須相信自己，這是成功的秘訣。

你的代码实现了一个处理森林中树的直径和合并操作的功能，但在加上 O2 优化后出现问题，可能是由于某些未定义行为或边界条件导致的。以下是一些可能的改进和调试建议：

初始化和边界条件：
确保所有数组和变量在使用前都被正确初始化。例如，deepest 和 deepest2 数组在合并树时可能没有被正确更新。
合并逻辑：
在合并两棵树时，确保你正确更新 deepest 和 deepest2 的值。特别是当两棵树的深度相等时，可能需要更仔细地处理。
**使用 std::vector**：
考虑使用 std::vector 替代手动管理的数组和链表，这样可以减少内存管理的复杂性，并且更容易避免越界错误。
调试输出：
在关键的地方添加调试输出，尤其是在合并操作和直径计算的地方，以便更好地理解程序的执行流程。
**避免使用 #define int long long**：
这种做法可能会导致一些意想不到的行为，尤其是在与 STL 容器交互时。建议使用 long long 类型的变量而不是全局替换。
检查递归深度：
如果树的深度很大，可能会导致栈溢出。考虑使用迭代的方法来替代递归。
优化合并操作：
在合并操作中，考虑使用更高效的数据结构（如并查集）来管理树的合并和查询。

以下是一个简化的代码示例，展示了如何使用 std::vector 和更清晰的合并逻辑：

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, depth, maxDepth, secondMaxDepth;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void dfs(int node, int par, int d) {
    depth[node] = d;
    for (int neighbor : adj[node]) {
        if (neighbor != par) {
            dfs(neighbor, node, d + 1);
        }
    }
}

void calculateDiameter(int root) {
    maxDepth[root] = 0;
    dfs(root, -1, 0);
    int farthestNode = max_element(depth.begin(), depth.end()) - depth.begin();
    fill(depth.begin(), depth.end(), 0);
    dfs(farthestNode, -1, 0);
    int diameter = *max_element(depth.begin(), depth.end());
    maxDepth[root] = diameter;
}

void mergeTrees(int x, int y) {
    // Implement merging logic here
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    parent.resize(n + 1);
    depth.resize(n + 1);
    maxDepth.resize(n + 1);
    secondMaxDepth.resize(n + 1);
    iota(parent.begin(), parent.end(), 0);

    // Read edges and build the forest
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        // Add edges to adjacency list
    }

    // Calculate diameters for each tree
    for (int i = 1; i <= n; i++) {
        if (parent[i] == i) {
            calculateDiameter(i);
        }
    }

    // Process queries
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            cout << maxDepth[find(x)] << endl;
        } else if (op == 2) {
            int x, y;
            cin >> x >> y;
            // Handle merging logic
        }
    }

    return 0;
}