放牧代码和思想
专注自然语言处理、机器学习算法

SPOJ QTREE5 Query on a tree V 题解《挑战程序设计竞赛》

目录

2015e.png挑战程序设计竞赛第二版.jpg

SPOJ QTREE5 Query on a tree V 

染色:给定一颗黑白树,请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。

2015e.png

4.6划分、解决、合并:分治法 

树上的分治法 

重心分解后,对每个子树root维护一个优先队列que,维护子树中各白点到root的距离。这样染黑色时可以快速从que中找到仍然是白色的第一个点。如果不用que,只用一个元素Path的话,染白色固然没问题,染黑色就麻烦了。

查询x时,遍历x所属子树root,按如下方式更新答案

ans = min(ans, dist(x, root) + dist_white(root)); // x到根节点+根节点到白点

至于如何求dist,可以参考POJ 1986 Distance Queries  题解《挑战程序设计竞赛》,用LCA快速实现。

另外需注意查询次数可能非常多,需要预处理出所有的重心,而不要来一个查询求一次重心。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define MAX_V 100004
#define MAX_LOG_V 16
#define INF 0x3f3f3f3f

vector<int> G[MAX_V];
// 重心分割
int subtree_size[MAX_V], centroid[MAX_V]; // -1未初始化,-2没有上级子树

void compute_subtree_size(int v, int p)
{
    subtree_size[v] = 1;

    for (int i = 0; i < G[v].size(); ++i)
    {
        int to = G[v][i];

        if (to != p && centroid[to] == -1)
        {
            compute_subtree_size(to, v);
            subtree_size[v] += subtree_size[to];
        }
    }
}

void search_centroid(int v, int p, int n, int prev_centroid)
{
    for (int i = 0; i < G[v].size(); ++i)
    {
        int to = G[v][i];

        if (to != p && centroid[to] == -1 && 2 * subtree_size[to] > n)
        {
            search_centroid(to, v, n, prev_centroid);
            return;
        }
    }

    centroid[v] = prev_centroid;

    for (int i = 0; i < G[v].size(); ++i)
    {
        int to = G[v][i];

        if (centroid[to] == -1)
        {
            compute_subtree_size(to, -1);
            search_centroid(to, v, subtree_size[to], v);
        }
    }
}

void init_centroid(int root)
{
    memset(centroid, -1, sizeof centroid);
    compute_subtree_size(root, -1);
    search_centroid(root, -1, subtree_size[root], -2);
}

struct Path
{
    int to, dist;

    inline bool operator<(const Path &other) const
    {
        return dist > other.dist;
    }
};

// LCA
int parent[MAX_LOG_V][MAX_V];  // 向上走2^k步所到的节点(超过根时记为-1)
int depth[MAX_V];              // 节点的深度

void dfs(int v, int p, int d)
{
    parent[0][v] = p;
    depth[v] = d;
    for (int i = 0; i < G[v].size(); i++)
    {
        if (G[v][i] != p)
            dfs(G[v][i], v, d + 1);
    }
}

// 预处理
void init_lca(int V)
{
    dfs(0, -1, 0);
    // 预处理出parent
    for (int k = 0; k + 1 < MAX_LOG_V; k++)
    {
        for (int v = 0; v < V; v++)
        {
            if (parent[k][v] < 0)
                parent[k + 1][v] = -1;
            else
            {
                parent[k + 1][v] = parent[k][parent[k][v]];
            }

        }
    }
}

// 计算u和v的LCA
int lca(int u, int v)
{
    // 让u和v向上走到同一深度
    if (depth[u] > depth[v])
        swap(u, v);
    for (int k = 0; k < MAX_LOG_V; k++)
    {
        if ((depth[v] - depth[u]) >> k & 1)
        {
            v = parent[k][v];
        }
    }
    if (u == v)
        return u;
    // 利用二分搜索计算LCA
    for (int k = MAX_LOG_V - 1; k >= 0; k--)
    {
        if (parent[k][u] != parent[k][v])
        {
            u = parent[k][u];
            v = parent[k][v];
        }
    }
    return parent[0][u];
}

int dist(int u, int v)
{
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

priority_queue<Path> que[MAX_V];   // que[centroid] := 中心centroid离子树中某个白点的路径
bool white[MAX_V];

int dist_white(int x)
{
    priority_queue<Path> &q = que[x];

    while (!q.empty())
    {
        Path cur = q.top();

        if (!white[cur.to])
        {
            q.pop();
        }
        else
        {
            return cur.dist;    // 最近的白点
        }
    }

    return INF;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("err.txt", "w", stderr);
#endif
    int N, Q;
    scanf("%d", &N);
    for (int i = 1, u, v; i < N; ++i)
    {
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init_centroid(1);
    init_lca(N);
    scanf("%d", &Q);
    int op, x;
    while (Q--)
    {
        scanf("%d %d", &op, &x);
        --x;
        if (op == 0)
        {
            white[x] = !white[x];

            if (white[x])
            {
                int root = x;
                while (root != -2)
                {
                    que[root].push(Path{x, dist(x, root)});   // 记录白点
                    root = centroid[root];
                }
            }
        }
        else
        {
            int ans = INF, root = x;
            while (root != -2)
            {
                ans = min(ans, dist(x, root) + dist_white(root)); // x到根节点+根节点到白点
                root = centroid[root];
            }
            printf("%d\n", ans == INF ? -1 : ans);
        }
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stderr);
#endif
    return 0;
}

hankcs.com 2017-02-02 下午11.41.00.png

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » SPOJ QTREE5 Query on a tree V 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机