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;
}
bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu