2016年4月

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;
}