noip2015_transport.cc

// Source code from laekov at noip 2015 day2 #define PRID “transport” #include #include #include #include

using namespace std;

const int maxn = 300003; const int maxl = 21;

const int buf_len = 45678; char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() {
if (++ bufb == bufe)
bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin);
} #define readInt(x) {
register int s(0), neg(0);
while (!isdigit(*bufb)) {
if (*bufb == ‘-’)
neg = 1;
readBuf();
}
do {
s = s * 10 + *bufb - 48;
readBuf();
} while (isdigit(*bufb));
if (neg)
x = -s;
else
x = s;
}

struct edge { int t, l; edge *ne; };

struct path { int u, v, a, l; }; inline bool cmpPath(const path& a, const path& b) { return a. l > b. l; }

struct heapM { int n, a[maxn]; heapM() { n = 0; } inline void push(int x) { a[n] = x; push_heap(a, a + (++ n)); } inline int top() { return n ? a[0] : -1; } inline void pop() { if (n) pop_heap(a, a + (n –)); } };

struct setR { heapM a, r; inline void insert(int x) { a. push(x); } inline void remove(int x) { r. push(x); } int query() { while (a. n && a. top() == r. top()) { a. pop(); r. pop(); } return a. top(); } };

int n, m; int ut[maxn][maxl], d[maxn], df[maxn], dr[maxn]; path a[maxn]; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn]; setR rs;

inline void addEdge(int u, int v, int w) { ebuf-> t = v; ebuf-> l = w; ebuf-> ne = head[u]; head[u] = ebuf ++; }

void buildBFS() { static int q[maxn]; int hd(0), tl(1); memset(d, 0, sizeof(d)); d[0] = 0; d[q[hd] = 1] = 1; dr[1] = df[1] = 0; for (int i = 0; i < maxl; ++ i) ut[0][i] = ut[1][i] = 0; while (hd < tl) { int p(q[hd ++]); for (int i = 1; i < maxl; ++ i) ut[p][i] = ut[ut[p][i - 1]][i - 1]; for (edge *e = head[p]; e; e = e-> ne) if (!d[e-> t]) { d[e-> t] = d[p] + 1; ut[e-> t][0] = p; df[e-> t] = e-> l; dr[e-> t] = dr[p] + e-> l; q[tl ++] = e-> t; } } }

int LCA(int u, int v) { if (d[u] < d[v]) swap(u, v); for (int i = maxl - 1; i >= 0; – i) if (d[ut[u][i]] >= d[v]) u = ut[u][i]; if (u == v) return u; for (int i = maxl - 1; i >= 0; – i) if (ut[u][i] ^ ut[v][i]) { u = ut[u][i]; v = ut[v][i]; } return ut[u][0]; }

inline bool onPath(int u, const path& p) { return LCA(u, p. a) == p. a && (LCA(u, p. u) == u || LCA(u, p. v) == u); }

int dqEnum() { static int q[maxn]; int hd(0), tl(d[a[0]. u] + d[a[0]. v] - d[a[0]. a] * 2 + 1); int ans; for (int i = 0, u = a[0]. u; u != a[0]. a; ++ i, u = ut[u][0]) { q[i] = u; rs. insert(df[u]); } q[d[a[0]. u] - d[a[0]. a]] = a[0]. a; for (int j = tl - 1, v = a[0]. v; v != a[0]. a; – j, v = ut[v][0]) { q[j] = v; rs. insert(df[v]); } a[m]. l = 0; if (!a[0]. l) return 0; ans = max(a[1]. l, a[0]. l - rs. query()); for (int i = 1; i < m && hd + 1 < tl; ++ i) { while (hd < tl && !onPath(q[hd], a[i])) { if (hd + 1 < tl) { if (d[q[hd]] > d[q[hd + 1]]) rs. remove(df[q[hd]]); else rs. remove(df[q[hd + 1]]); } ++ hd; } while (hd < tl && !onPath(q[tl - 1], a[i])) { if (hd + 1 < tl) { if (d[q[tl - 1]] > d[q[tl - 2]]) rs. remove(df[q[tl - 1]]); else rs. remove(df[q[tl - 2]]); } – tl; } if (hd + 1 < tl) ans = min(ans, max(a[0]. l - rs. query(), a[i + 1]. l)); } return ans; }

int main() { freopen(PRID “.in”, “r”, stdin); freopen(PRID “.out”, “w”, stdout);

memset(head, 0, sizeof(head));
readInt(n);
readInt(m);
for (int i = 1; i < n; ++ i) {
	int u, v, w;
	readInt(u);
	readInt(v);
	readInt(w);
	addEdge(u, v, w);
	addEdge(v, u, w);
}
buildBFS();
for (int i = 0; i < m; ++ i) {
	readInt(a[i]. u);
	readInt(a[i]. v);
	a[i]. a = LCA(a[i]. u, a[i]. v);
	a[i]. l = dr[a[i]. u] + dr[a[i]. v] - dr[a[i]. a] * 2;
}
sort(a, a + m, cmpPath);
printf("%d\n", dqEnum());

}

Comments