SSL 2687_树_线段树

发布于 2017-08-10  940 次阅读

题目描述

给你一棵大小为n的有根树，每个点有点权，要求完成以下操作： 
V x y把点x的权值变成y 
E x把有根树的根变为x 
Q x查询点x的子树的最小值 

 

思路

可以将这棵树跑一边dfs序然后建一棵线段树，对于每一个点的单点修改和查询用线段树实现起来还是比较简单的

问题就在于如何实现换根，我们可以使根节点一直为1来进行处理

我们无论如何都可以将答案转化为一个在以1为根的树上进行查找，可能分为两个区间，也可能只在一个区间中查找

#include 
#include 
#define maxn 100001
#define INF 0x7f7f7f7f
#define min(x, y) (x) < (y) ? (x) : (y)
int n, m;
struct edge
{
    int to, next;
}e[maxn * 2];
int ls[maxn * 2], a[maxn], b[maxn], first[maxn], last[maxn], t[maxn * 4 + 1], root;
bool fl[maxn];
int dep = 1;
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int dfs(int x)
{
    first[x] = dep;
    b[first[x]] = a[x];
    for (int i = ls[x]; i; i = e[i].next)
        if (!fl[e[i].to])
        {
            fl[e[i].to] = 1;
            dep++;
            dfs(e[i].to);
        }
    last[x] = dep;
}
int make(int p, int l, int r)
{
    int m = (l + r) >> 1;
    if (l == r)
    {
        t[p] = b[l];
        return 0;
    }
    make(p << 1, l, m);
    make(p << 1 | 1, m + 1, r);
    t[p] = min(t[p << 1], t[p << 1 | 1]);
}
int change(int p, int l, int r, int x, int w)
{
    if (l == r)
    {
        t[p] = w;
        return 0;
    }
    int m = (l + r) >> 1;
    if (x <= m) change(p << 1, l, m, x, w);
    else change(p << 1 | 1, m + 1, r, x, w);
    t[p] = min(t[p << 1], t[p << 1 | 1]);
}
int find(int p, int l, int r, int x, int y)
{
    if (x > y || y < 1 || x > n) return INF;
    if (l == x && r == y)
    {
        return t[p];
    }
    int m = (l + r) >> 1;
    if (y <= m) return find(p << 1, l, m, x, y);
    else if (x > m) return find(p << 1 | 1, m + 1, r, x, y);
    else return min(find(p << 1, l, m, x, m), find(p << 1 | 1, m + 1, r, m + 1, y));
}
int getans(int x)
{
    int xx;
    if (first[x] <= first[root] && last[x] >= last[root])
    {
        for (int i = ls[x]; i; i = e[i].next)
            if (first[e[i].to] <= first[root] && last[e[i].to] >= last[root])
            {
                xx = e[i].to;
                break;
            }
        return min(find(1, 1, n, 1, last[xx] - 1), find(1, 1, n, first[xx] + 1, n));
    }
    else return find(1, 1, n, first[x], last[x]);
}
int main()
{
    scanf("%d%d", &n, &m);
    int l = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = read(), y = read();
        a[i] = y;
        if (i != 1)
        {
            e[++l] = (edge) {x, ls[i]};
            ls[i] = l;
            e[++l] = (edge) {i, ls[x]};
            ls[x] = l;
        }
    }
    fl[1] = 1;
    dfs(1);
    make(1, 1, n);
    root = 1;
    for (int i = 1; i <= m; i++)
    {
        char ch;
        std:: cin >> ch;
        if (ch == 'V') 
        {
            int x = read(), y = read();
            change(1, 1, n, first[x], y);
        }
        else if (ch == 'E') 
        {
            int x = read();
            root = x;
        }
        else
        {
            int x = read();
            printf("%d\n", getans(x));
        }
    }
}

 

]]>