2016年1月

在年末之前学会了如此黑科技,也算是一个比较好的结尾吧。
【此处占坑写教程】

贴代码。

代码

SPOJ QTREE

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

template<class T>
void read(T& x)
{
    char ch = getchar(); T p = 1, n = 0;
    while(ch < '0' || ch > '9'){if(ch == '-') p = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
    x = p * n;
}
template<class T, class U>
void read(T& x, U& y)
{
    read(x), read(y);
}
template<class T, class U, class V>
void read(T& x, U& y, V& z)
{
    read(x), read(y), read(z);
}

const int inf = 0x3f3f3f3f, maxn = 1e5;
int n;

namespace ZKW
{
    struct Info
    {
        int max;
        Info(int x = -inf) : max(x) {}
        Info operator+(const Info& b)
        {
            return Info(::max(max, b.max));
        }
    } I[maxn];

    int t = 1;
    void init(){while(t <= n + 3) t <<= 1;memset(I, 0, sizeof I);}

    void modify(int u, int w)
    {
        for(I[u += t] = Info(w), u >>= 1; u; u >>= 1)
            I[u] = I[u * 2] + I [u * 2 + 1];
    }

    int query(int u, int v)
    {
        Info ret;
        for(u += t - 1, v += t + 1; u ^ v ^ 1; u >>= 1, v >>= 1)
        {
            if(~u & 1)
                ret = ret + I[u ^ 1];
            if(v & 1)
                ret = ret + I[v ^ 1];
        }
        return ret.max;
    }
}

struct Edge
{
    int to, w;
    Edge* next;
    Edge(int t = 0, int _w = 0) : to(t), w(_w){}
} pool[maxn * 2], *header[maxn];

int cnt = 0;
void add_edge(int u, int v, int w)
{
    Edge *newedge = &pool[cnt++];
    newedge -> to = v;
    newedge -> w = w;
    newedge -> next = header[u];
    header[u] = newedge;
}

int fa[maxn] = {0}, size[maxn] = {0}, hson[maxn] = {0}, depth[maxn] = {0};
void dfs(int i = 1)
{
    size[i] = 1, hson[i] = 0;
    for(Edge* e = header[i]; e; e = e -> next)
    {
        if(e -> to != fa[i])
        {
            fa[e -> to] = i;
            depth[e -> to] = depth[i] + 1;
            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}, nc = 1;
void build_tree(int i = 1, int tp = 1)
{
    number[i] = nc++, top[i] = tp;
    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 query(int u, int v)
{
    int tu = top[u], tv = top[v];
    int ret = -inf;
    while(tu != tv)
    {
        if(depth[tu] < depth[tv])
            swap(tu, tv), swap(u, v);
        ret = max(ret, ZKW::query(number[tu], number[u]));
        u = fa[tu]; tu = top[u];
    }
    if(u == v)
        return ret;
    if(depth[u] > depth[v])
        swap(u, v);
    return max(ret, ZKW::query(number[hson[u]], number[v]));
}

int u[maxn] = {0}, v[maxn] = {0}, w[maxn] = {0};
int main()
{
    int t;
    read(t);
    while(t--)
    {
        cnt = 0, nc = 1;
        memset(header+1, 0, sizeof(*header)*n);
        read(n);
        for(int i = 1; i < n; i++)
        {
            read(u[i], v[i], w[i]);
            add_edge(u[i], v[i], w[i]);
            add_edge(v[i], u[i], w[i]);
        }
        dfs();
        build_tree();
        ZKW::init();
        for(int i = 1; i < n; i++)
        {
            if(depth[u[i]] < depth[v[i]])
                swap(u[i], v[i]);
            ZKW::modify(number[u[i]], w[i]);
        }
        char s[10];
        while(scanf("%s", s) && s[0] != 'D')
        {
            int a, b; read(a, b);
            if(s[0] == 'C')
                ZKW::modify(number[u[a]], b);
            else
                printf("%d\n", query(a, b));
        }
    }
    return 0;
}

2016君,敬启。见安。
原以为你离我很远,没想到就在毫无准备中我们见面了。
对于你的到来,我仅仅只是心存敬意。
我知道你是2015的后继,也是人为定制的界限。
每一年都是重要的,你也不例外。
我希望在你即将走的时候,我可以对你感叹一声「今年我努力过」。
对此,我会加油的。