【CodeForces】343D Water tree （线段树好题！还未弄懂）

/* 此题的方法除了用线段树求子树，通过标记父亲，更新儿子的方法，来更新祖先，学习了。 对于建树的方法由于并没有说明父亲与儿子的顺序，所以需要通过两次添加。 并且pre变量可以获得父亲的位置，还未弄懂！ */
#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 500005
#define ls rt<<1
#define rs ls|1
#define m (l+r)>>1
int sum[MAX << 2];
int col[MAX << 2];
int fa[MAX << 2];
int head[MAX];
int num;
int time;

struct tree
{
    int v, next;
}edg[MAX<<2];

struct f
{
    int s, e;
}s[MAX];

void addedge(int a, int b)
{
    edg[num].v = b;
    edg[num].next = head[a];
    head[a] = num++;
}

void dfs(int a, int pre)
{
    fa[a] = pre;
    s[a].s = ++time;
    for (int i = head[a]; i != -1; i = edg[i].next)
    {
        if (edg[i].v == pre)continue;
        dfs(edg[i].v, a);
    }
    s[a].e = time;
}

void uprt(int rt)
{
    sum[rt] = sum[ls] && sum[rs];
}

void uprt2(int rt)
{
    if (col[rt] == 1)
    {
        sum[rs] = sum[ls] = col[rt];
        col[rs] = col[ls] = col[rt];
        col[rt] = -1;
    }
}
void updata(int L, int R, int c, int l, int r, int rt)
{
    if (L <= l&&r <= R)
    {
        col[rt] = c;
        sum[rt] = c;
        return;
    }
    uprt2(rt);
    int mid = m;
    if (L <= mid)
        updata(L, R, c, l, mid, ls);
    if (mid < R)
        updata(L, R, c, mid + 1, r, rs);
    uprt(rt);
}

void updata(int q, int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = 0;
        return;
    }
    uprt2(rt);
    int mid = m;
    if (q <= mid)
        updata(q, l, mid, ls);
    if (mid < q)
        updata(q, mid + 1, r, rs);
    uprt(rt);
}
int query(int L,int R, int l, int r, int rt)
{

    if (L<=l&&r<=R)
        return sum[rt];
    uprt2(rt);
    int mid = m;
    int a = 0x7fff, b = 0x7fff;
        if(L<=mid)a=query(L,R, l, mid, ls);
        if(R>mid)b=query(L,R, mid + 1, r, rs);
        return min(a, b);
}

int main()
{
    int n;
    while (~scanf("%d",&n))
    {
        num = 0;
        time = 0;
        memset(head, -1, sizeof(head));
        int a, b;
        memset(sum, 0, sizeof(sum));
        memset(col, -1, sizeof(col));
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d", &a, &b);
            addedge(a, b);
            addedge(b, a);
        }
        dfs(1, -1);
        int c;
        int t;
        cin >> t;
        bool tg = true;
        while (t--)
        {
            scanf("%d%d", &c, &a);
            if (c == 1)
            {
                //这个操作的作用是由于要将一个点变为1，那么假如这个点原来是0的话，那么他的祖先都是0
                //但是没办法一下子全部修改祖先，所以就只能够在更新一个0的节点为1的时候将他的父亲变为0，这样就可以保持下去
                //绝妙！！
                if (!query(s[a].s, s[a].e, 1, n, 1) && fa[a] != -1)
                {

                    updata(s[fa[a]].s, 1, n, 1);
                }
                updata(s[a].s, s[a].e, 1, 1, n, 1);
            }
            else if (c == 2)
            {
                updata(s[a].s, 1, n, 1);
            }
            else if (c == 3)
            {

                printf("%d\n", query(s[a].s, s[a].e, 1, n, 1));
            }
        }
    }
}