最適化による結果の違いの原因を知りたい。

前提・実現したいこと

プログラミング学習としてこちらの問題を解こうとしています。
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0391?year=2018

発生している問題・エラーメッセージ

自分の環境でコードを実行すると正解が出るのですが、サイト上の判定ではWA(wrong answer)が出ます。
最適化の有無が原因だと考えられるのですが、どのような状況下で最適化による影響が出るのか教えていただけると幸いです。

該当のソースコード

C
1#include <stdio.h>
2#include <stdlib.h>
3#define N_MAX 100010
4
5int parent[100005];
6
7int depth[100005];
8int dist[100005];
9
10int p[30][100005];
11
12typedef struct lst
13{
14    struct lst *next;
15    int to;
16    int cost;
17} LIST;
18
19LIST list[N_MAX];
20
21LIST *newnode(void)
22{
23    LIST *p;
24    p = malloc(sizeof(LIST));
25    if (p != NULL)
26    {
27        p->next = NULL;
28    }
29}
30
31LIST *add(LIST *p, int to, int cost)
32{
33    while (p->next != NULL)
34    {
35        p = p->next;
36    }
37    if ((p->next = newnode()) != NULL)
38    {
39        p->to = to;
40        p->cost = cost;
41    }
42    return p;
43}
44
45int max(int a, int b)
46{
47    return a > b ? a : b;
48}
49
50int min(int a, int b)
51{
52    return b > a ? a : b;
53}
54
55void swap(int *a, int *b)
56{
57    int temp;
58    temp = *a;
59    *a = *b;
60    *b = temp;
61}
62
63
64void dfs(int pos, int prev, int Depth, int Dist)
65{
66    parent[pos] = prev;
67    depth[pos] = Depth;
68    dist[pos] = Dist;
69    LIST *p;
70    
71    for(p = &list[pos];p->next != NULL;p=p->next){
72        LIST e;
73        e.to = p->to;
74        e.cost = p->cost;
75        if(e.to == prev)
76            continue;
77        dfs(e.to, pos, Depth + 1, Dist + e.cost);
78    }
79    return;
80}
81
82int lca(int a, int b)
83{
84    if (depth[a] > depth[b])
85        swap(&a, &b);
86
87    int s = (depth[b] - depth[a]);
88    for (int i = 0; i < 30; i++)
89        if (s >> i & 1)
90            b = p[i][b];
91
92    if (a == b)
93        return a;
94
95    for (int i = 29; i >= 0; i--)
96    {
97        if (p[i][a] != p[i][b])
98        {
99            a = p[i][a];
100            b = p[i][b];
101        }
102    }
103    return parent[a];
104}
105
106int calc_dist(int a, int b)
107{
108    int c = lca(a, b);
109    return dist[a] - dist[c] + dist[b] - dist[c];
110}
111
112int check(int p, int a, int b, int c)
113{
114    int res = 0;
115    res = max(res, calc_dist(p, a));
116    res = max(res, calc_dist(p, b));
117    res = max(res, calc_dist(p, c));
118    return res;
119}
120
121int solve(int a, int b, int c)
122{
123    int x = lca(b, c);
124    if (calc_dist(x, b) > calc_dist(x, c))
125        swap(&b, &c);
126
127    int y = calc_dist(b, c) / 2;
128    int z = c;
129    for (int i = 29; i >= 0; i--)
130    {
131        int nz = p[i][z];
132        if (nz != -1 && (dist[c] - dist[nz]) <= y)
133        {
134            z = nz;
135        }
136    }
137
138    int res = check(z, a, b, c);
139    if (parent[z] != -1)
140        res = min(res, check(parent[z], a, b, c));
141    return res;
142}
143
144int main(void)
145{
146    int N, Q;
147    int u, v, w;
148    int a, b, c;
149
150    scanf("%d %d", &N, &Q);
151    for (int i = 1; i < N; i++)
152    {
153        scanf("%d %d %d", &u, &v, &w);
154        u--;
155        v--;
156        add(&list[u], v, w);
157        add(&list[v], u, w);
158    }
159
160    dfs(1, -1, 0, 0);
161
162    for (int i = 0; i < N; i++)
163        p[0][i] = parent[i];
164
165    for (int i = 1; i < 30; i++)
166    {
167        for (int j = 0; j < N; j++)
168        {
169            int x = p[i - 1][j];
170            if (x != -1)
171                x = p[i - 1][x];
172            p[i][j] = x;
173        }
174    }
175
176    for (int i = 0; i < Q; i++)
177    {
178        scanf("%d %d %d", &a, &b, &c);
179        a--;
180        b--;
181        c--;
182        int ans = (1 << 30);
183        ans = min(ans, solve(a, b, c));
184        ans = min(ans, solve(b, a, c));
185        ans = min(ans, solve(c, b, a));
186        printf("%d\n", ans);
187    }
188    
189    return 0;
190}