我在这份代码中 :
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#define int long long
#define INF (0x3f3f3f3f)
using namespace std;
char buf[3000000], *p1 = buf, *p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,3000000,stdin),p1==p2)?EOF:*p1++)
inline int read() {
int x = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return x;
}
const int MAXN = 1000005;
int n, Q;
struct edge {
int to, nex, dis;
}e[MAXN]; int idx, head[MAXN];
inline void add(int u, int v, int w) {
e[++ idx].to = v;
e[idx].dis = w;
e[idx].nex = head[u];
head[u] = idx;
}
namespace Prew {
int timer, dep[MAXN];
int dfn[MAXN], eu[MAXN];
int lg[MAXN], f[MAXN][25];
inline void dfs(int u, int fath) {
eu[dfn[u] = ++ timer] = u;
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to;
if (v == fath) continue;
dep[v] = dep[u] + e[i].dis;
dfs(v, u), eu[++ timer] = u;
}
}
inline int _min(const int &x, const int &y) {
return dep[x] < dep[y] ? x : y;
}
inline void Init() {
for (int i = 1; i <= timer; ++ i)
f[i][0] = eu[i];
for (int i = 2; i <= timer; ++ i)
lg[i] = lg[i >> 1] + 1;
for (int j = 1; j <= lg[timer]; ++ j)
for (int i = 1; i <= timer; ++ i) {
f[i][j] = f[i][j - 1];
if (i + (1 << (j - 1)) <= timer)
f[i][j] = _min(f[i][j], f[i + (1 << (j - 1))][j - 1]);
}
}
inline int Getlca(int u, int v) {
int l = min(dfn[u], dfn[v]);
int r = max(dfn[u], dfn[v]);
int len = lg[r - l + 1];
return _min(f[l][len], f[r - (1 << len) + 1][len]);
}
inline int dist(int u, int v) {
int lca = Getlca(u, v);
return dep[u] + dep[v] - dep[lca] - dep[lca];
}
inline void prewmain() {
n = read();
for (int i = 1; i < n; ++ i) {
int u = read(), v = read(), w = read();
add(u, v, w); add(v, u, w);
}
dfs(1, 0); Init();
}
}
struct Points {
int x, y;
}a[MAXN * 20]; int pn;
namespace Getpts {
int nd[MAXN], tp;
int siz[MAXN], fg[MAXN];
inline void dfs1(int u, int fath) {
nd[++ tp] = u, siz[u] = 1;
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to;
if (v == fath || fg[v]) continue;
dfs1(v, u); siz[u] += siz[v];
}
}
inline int Getrt(int x) {
tp = 0; dfs1(x, 0);
int nw = x, res = tp;
for (int i = 1; i <= tp; ++ i)
if (max(siz[nd[i]], tp - siz[nd[i]]) < res)
nw = nd[i], res = max(siz[nd[i]], tp - siz[nd[i]]);
return nw;
}
int dep[MAXN];
inline void dfs2(int u, int fath) {
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to;
if (v == fath || fg[v]) continue;
dep[v] = dep[u] + e[i].dis;
dfs2(v, u);
}
}
int stc[MAXN], top;
inline void Solve(int rt) {
dep[rt] = 0; dfs2(rt, 0);
sort(nd + 1, nd + tp + 1);
top = 0;
for (int i = 1; i <= tp; ++ i) {
while (top && dep[nd[i]] < dep[stc[top]])
-- top;
if (top) a[++ pn] = (Points){stc[top], nd[i]};
stc[++ top] = nd[i];
}
top = 0;
for (int i = tp; i; -- i) {
while (top && dep[nd[i]] < dep[stc[top]])
-- top;
if (top) a[++ pn] = (Points){nd[i], stc[top]};
stc[++ top] = nd[i];
}
fg[rt] = 1;
for (int i = head[rt]; i; i = e[i].nex)
if (!fg[e[i].to]) Solve(Getrt(e[i].to));
}
inline void getmain() {
Solve(Getrt(1));
}
}
class BIT {
private :
int tr[MAXN];
inline int lowbit(int x) {
return (x & (-x));
}
public :
inline BIT() {
memset(tr, 0x3f, sizeof(tr));
}
inline void Modify(int p, int x) {
for (; p; p -= lowbit(p))
tr[p] = min(tr[p], x);
}
inline int Query(int p) {
int res = INF;
for (; p <= n; p += lowbit(p))
res = min(res, tr[p]);
return res;
}
};
struct Qry {
int l, r, id;
inline bool operator < (const Qry &y) const {
return r < y.r;
}
}q[MAXN];
namespace Ansq {
BIT st;
int ans[MAXN];
vector<Points>vec[MAXN];
inline void Solve() {
Q = read();
for (int i = 1; i <= Q; ++ i)
q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(q + 1, q + Q + 1);
for (int i = 1; i <= pn; ++ i)
vec[a[i].y].push_back(a[i]);
int pt = 1;
for (int i = 1; i <= Q; ++ i) {
for (; pt <= q[i].r; ++ pt)
for (Points u : vec[pt])
st.Modify(u.x, Prew::dist(u.x, u.y));
ans[q[i].id] = st.Query(q[i].l);
}
for (int i = 1; i <= Q; ++ i)
printf ("%lld\n", ans[i] == INF ? -1 : ans[i]);
}
}
signed main()
{
Prew::prewmain();
Getpts::getmain();
Ansq::Solve();
return 0;
}
错误地定义了 long long 的 INF 为 0x3f3f3f3f ,但是在 devcpp 却能输出正确的结果,甚至我在极限数据下对拍了 3 分钟都没有出错。
我已经开启了 -Wall 指令,却没有什么用处,请问什么办法可以避免这种错误?