2013-team4/code/block-tree

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
SPOJ QTREE
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

We will ask you to perfrom some instructions of the following form:

* CHANGE i ti : change the cost of the i-th edge to ti
* QUERY a b : ask for the maximum edge cost on the path from node a to node b
}}}

{{{
参考资料:http://hi.baidu.com/wjbzbmr/item/b17cb3bb06b4fc4a2bebe32a
块状树做法，将树分成sqrt{N}块，每块大小sqrt{N}
对于单点修改, 直接暴力在这个块中修改就可以了, 时间复杂度sqrt{N}
对于查询操作, 同一块中直接暴力查询，不同块就利用记录的信息跨块查询，时间复杂度sqrt{N}
}}}
{{{
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define PB push_back
#define MP make_pair

using namespace std;

typedef pair<int, int> PII;

const int MAXN=10005;
const int inf=100000000;

vector<PII> E[MAXN];
vector<int> ET[MAXN];
int to[MAXN], own[MAXN], fa[MAXN], dep[MAXN];
int size[MAXN], mm[MAXN], val[MAXN];
int edge[MAXN];
int L, N;

inline int get()
{
    char ch;
    while (ch=getchar(), (ch<'0'||ch>'9'));
    int ret=ch-'0';
    while (ch=getchar(), (ch>='0'&&ch<='9')) ret=ret*10+ch-'0';
    return ret;
}

void build(int u, int f, int d)
{
    dep[u]=d; fa[u]=f;
    int tmp=own[u];
    for (int i=0; i<E[u].size(); i++)
    {
        int v=E[u][i].first, id=E[u][i].second;
        if (v==f) continue;
        to[id]=v; val[v]=edge[id];
        if (size[tmp]<L) ET[u].PB(v), own[v]=tmp, size[tmp]++;
        build(v, u, d+1);

    }
}

void dfs(int u, int m)
{
    m=max(m, val[u]); mm[u]=m;
    for (int i=0; i<ET[u].size(); i++)
        dfs(ET[u][i], m);
}

void change(int id, int value)
{
    int u=to[id]; val[u]=value;
    if (own[u]==u) dfs(u, -inf);
    else dfs(u, mm[fa[u]]);
}

int query(int a, int b)
{
    int M=-inf;
    while (a!=b)
    {
        if (dep[a]<dep[b]) swap(a, b);
        if (own[a]==own[b]) M=max(M, val[a]), a=fa[a];
        else
        {
            if (dep[own[a]]<dep[own[b]]) swap(a, b);
            M=max(M, mm[a]); a=fa[own[a]];
        }
    }
    return M;
}

int main()
{
    int T=get();
    while (T--)
    {
        N=get(); L=sqrt(N)+1;
        for (int i=0; i<N; i++) E[i].clear(), ET[i].clear(), size[i]=0, own[i]=i;
        for (int u, v, w, i=1; i<N; i++)
        {
            u=get(); v=get(); w=get(); u--, v--;
            E[u].PB(MP(v, i)); E[v].PB(MP(u, i)); edge[i]=w;
        }
        build(0, -1, 0);
        for (int i=0; i<N; i++)
            if (own[i]==i) dfs(i, -inf);
        char st[100];
        while (scanf("%s", st)&&st[0]!='D')
        {
            int u, v;
            u=get(); v=get();
            if (st[0]=='C') change(u, v);
            else printf("%d\n", query(u-1, v-1));
        }
    }
    return 0;
}
}}}

SPOJ QTREE
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:
* CHANGE i ti : change the cost of the i-th edge to ti
* QUERY a b : ask for the maximum edge cost on the path from node a to node b

参考资料:http://hi.baidu.com/wjbzbmr/item/b17cb3bb06b4fc4a2bebe32a
块状树做法，将树分成sqrt{N}块，每块大小sqrt{N}
对于单点修改, 直接暴力在这个块中修改就可以了, 时间复杂度sqrt{N}
对于查询操作, 同一块中直接暴力查询，不同块就利用记录的信息跨块查询，时间复杂度sqrt{N}

#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define PB push_back
#define MP make_pair
using namespace std;
typedef pair<int, int> PII;
const int MAXN=10005;
const int inf=100000000;
vector<PII> E[MAXN];
vector<int> ET[MAXN];
int to[MAXN], own[MAXN], fa[MAXN], dep[MAXN];
int size[MAXN], mm[MAXN], val[MAXN];
int edge[MAXN];
int L, N;
inline int get()
{
    char ch;
    while (ch=getchar(), (ch<'0'||ch>'9'));
    int ret=ch-'0';
    while (ch=getchar(), (ch>='0'&&ch<='9')) ret=ret*10+ch-'0';
    return ret;
}
void build(int u, int f, int d)
{
    dep[u]=d; fa[u]=f;
    int tmp=own[u];
    for (int i=0; i<E[u].size(); i++)
    {
        int v=E[u][i].first, id=E[u][i].second;
        if (v==f) continue;
        to[id]=v; val[v]=edge[id];
        if (size[tmp]<L) ET[u].PB(v), own[v]=tmp, size[tmp]++;
        build(v, u, d+1);
    }
}
void dfs(int u, int m)
{
    m=max(m, val[u]); mm[u]=m;
    for (int i=0; i<ET[u].size(); i++)
        dfs(ET[u][i], m);
}
void change(int id, int value)
{
    int u=to[id]; val[u]=value;
    if (own[u]==u) dfs(u, -inf);
    else dfs(u, mm[fa[u]]);
}
int query(int a, int b)
{
    int M=-inf;
    while (a!=b)
    {
        if (dep[a]<dep[b]) swap(a, b);
        if (own[a]==own[b]) M=max(M, val[a]), a=fa[a];
        else
        {
            if (dep[own[a]]<dep[own[b]]) swap(a, b);
            M=max(M, mm[a]); a=fa[own[a]];
        }
    }
    return M;
}
int main()
{
    int T=get();
    while (T--)
    {
        N=get(); L=sqrt(N)+1;
        for (int i=0; i<N; i++) E[i].clear(), ET[i].clear(), size[i]=0, own[i]=i;
        for (int u, v, w, i=1; i<N; i++)
        {
            u=get(); v=get(); w=get(); u--, v--;
            E[u].PB(MP(v, i)); E[v].PB(MP(u, i)); edge[i]=w;
        }
        build(0, -1, 0);
        for (int i=0; i<N; i++)
            if (own[i]==i) dfs(i, -inf);
        char st[100];
        while (scanf("%s", st)&&st[0]!='D')
        {
            int u, v;
            u=get(); v=get();
            if (st[0]=='C') change(u, v);
            else printf("%d\n", query(u-1, v-1));
        }
    }
    return 0;
}