NOIP2015 运输计划
感觉还是一道不错的题的……花了两个晚上研(看)究(题解)做了出来。
对树剖的理解深刻了不少,以及了解了前缀和差分的妙用方法。
以及,一定要记住检查循环上限的变量名!!!
跟大神@plm交流一下思路,@plm表示不屑于树剖写法,自己写了LCA和树上差分,先膜。
哪天智商上线了并且学会非树剖LCA后我再试一试@plm的写法咯。
在UOJ测TLE了一个hack点只剩97,BZOJ莫名WA,洛谷RE爆栈了3个点,这个据说在NOIP不虚。
总之那么似乎看起来没有问题了?
UPD: 一怒之下把所有DFS改成BFS后洛谷A了,但UOJ和BZOJ还是处于莫名状态。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
inline int max(int a, int b)
{
return a > b ? a : b;
}
inline void swap(int &a, int &b)
{
int t = a; a = b; b = t;
}
template<class T>
inline void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 3e5 + 10;
int n, m;
struct Edge
{
int to, w;
Edge *next;
Edge(int v = 0, int ww = 0, Edge *n = 0) : to(v), w(ww), next(n) {}
} pool[maxn * 4], *header[maxn];
int pcnt = 0;
void add_edge(int u, int v, int w)
{
Edge *e = &pool[pcnt++];
*e = Edge(v, w, header[u]);
header[u] = e;
}
int depth[maxn] = {0}, fa[maxn] = {0}, size[maxn] = {0}, hson[maxn] = {0};
int w[maxn] = {0};
void dfs(int i = 1)
{
hson[i] = 0; size[i] = 1;
for(Edge *e = header[i]; e; e = e -> next)
if(e -> to != fa[i])
{
depth[e -> to] = depth[i] + 1;
fa[e -> to] = i;
w[e -> to] = e -> w;
dfs(e -> to);
size[i] += size[e -> to];
if(size[e -> to] > size[hson[i]])
hson[i] = e -> to;
}
}
int top[maxn] = {0}, number[maxn] = {0}, ncnt = 1;
int P[maxn] = {0};
void build_tree(int i = 1, int tp = 1)
{
top[i] = tp; number[i] = ncnt;
P[ncnt] = P[ncnt - 1] + w[i];
ncnt++;
if(hson[i])
build_tree(hson[i], tp);
for(Edge *e = header[i]; e; e = e -> next)
if(e -> to != fa[i] && e -> to != hson[i])
build_tree(e -> to, e -> to);
}
int queue[maxn] = {0}, qcnt = 1;
vector<int> ch[maxn];
void bfs()
{
queue[qcnt++] = 1;
for(int head = 1; head ^ qcnt; head++)
{
int i = queue[head];
for(Edge *e = header[i]; e; e = e -> next)
if((e -> to) ^ fa[i])
{
depth[e -> to] = depth[i] + 1;
fa[e -> to] = i;
w[e -> to] = e -> w;
queue[qcnt++] = e -> to;
}
}
for(int head = qcnt - 1; head ^ 0; head--)
{
int i = queue[head]; size[i] = 1, hson[i] = 0;
for(Edge *e = header[i]; e; e = e -> next)
if((e -> to) ^ fa[i])
{
size[i] += size[e -> to];
if(size[e -> to] > size[hson[i]])
hson[i] = e -> to;
}
}
top[1] = 1, number[1] = ncnt++;
ch[1].push_back(1);
for(int head = 1; head ^ qcnt; head++)
{
int i = queue[head];
for(Edge *e = header[i]; e; e = e -> next)
if((e -> to) ^ fa[i])
{
if(hson[i] == (e -> to))
top[e -> to] = top[i];
else
top[e -> to] = e -> to;
ch[top[e -> to]].push_back(e -> to);
}
}
for(int i = 1; i <= n; i++)
for(int j = 0; j ^ ch[i].size(); j++)
{
number[ch[i][j]] = ncnt;
P[ncnt] = w[ch[i][j]] + P[ncnt - 1];
ncnt++;
}
}
int dis(int u, int v)
{
int tu = top[u], tv = top[v];
int ret = 0;
while(tu ^ tv)
{
if(depth[tu] < depth[tv])
swap(u, v), swap(tu, tv);
ret += P[number[u]] - P[number[tu] - 1];
u = fa[tu], tu = top[u];
}
if(u == v)
return ret - (P[number[u]] - P[number[u] - 1]);
if(depth[u] < depth[v])
swap(u, v);
return ret + P[number[u]] - P[number[v]];
}
int D[maxn] = {0};
void modify(int u, int v)
{
int tu = top[u], tv = top[v];
while(tu ^ tv)
{
if(depth[tu] < depth[tv])
swap(u, v), swap(tu, tv);
D[number[tu]]++, D[number[u] + 1]--;
u = fa[tu], tu = top[u];
}
if(u == v)
return;
if(depth[u] < depth[v])
swap(u, v);
D[number[hson[v]]]++, D[number[u] + 1]--;
}
int d[maxn] = {0}, u[maxn] = {0}, v[maxn] = {0};
bool check(int x)//ma - x <= w
{
memset(D, 0, sizeof D);
int cnt = 0, ma = 0, sum = 0, maa = 0;
for(int i = 0; i ^ m; i++)
if(d[i] > x)
cnt++, ma = max(d[i] - x, ma), modify(u[i], v[i]);
for(int i = 0; i ^ n; i++)
{
sum += D[i];
if(sum == cnt && (P[i] - P[i - 1]) >= ma)
return true;
}
return false;
}
int main()
{
read(n, m);
for(int i = 1, a, b, t; i ^ n; i++)
{
read(a, b, t);
add_edge(a, b, t);
add_edge(b, a, t);
}
//dfs();
//build_tree();
bfs();
int l = 0, r = 0;
for(int i = 0; i ^ m; i++)
{
read(u[i], v[i]);
d[i] = dis(u[i], v[i]);
r = max(r, d[i]);
}
int ans = 0;
while(l <= r)
{
int mi = (l + r) >> 1;
if(check(mi))
ans = mi, r = mi - 1;
else
l = mi + 1;
}
printf("%d\n", ans);
return 0;
}