BZOJ 3531 SDOI 2014 旅行

題目大意

給出一個樹，樹上每個節點有兩個權值，分别是這個節點的宗教評級和這個節點信仰的宗教。多次修改這兩個權值，每次詢問樹上路徑上的點的同一個宗教的最大評級和評級和。

思路

不要想太多，每個宗教建立一顆線段樹，空間開不下考慮一下動态節點線段樹。之後在每個線段樹上維護一下樹鍊剖分就行了。

你們想知道c的取值範圍麼？

[0,10^5]

CODE

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
using namespace std;

struct SegTree *nil;

struct SegTree{
    SegTree *son[];
    int _max,sum;

    SegTree() {
        _max = sum = ;
        son[] = son[] = nil;
    }

    void Modify(int l,int r,int x,int c) {
        if(l == r) {
            _max = sum = c;
            return ;
        }
        int mid = (l + r) >> ;
        if(x <= mid) {   
            if(son[] == nil)
                son[] = new SegTree();
            son[]->Modify(l,mid,x,c);
        }
        else {
            if(son[] == nil)
                son[] = new SegTree();
            son[]->Modify(mid + ,r,x,c);
        }
        _max = max(son[]->_max,son[]->_max);
        sum = son[]->sum + son[]->sum;
    }
    int GetSum(int l,int r,int x,int y) {
        if(this == nil) return ;
        if(l == x && y == r)    return sum;
        int mid = (l + r) >> ;
        if(y <= mid) return son[]->GetSum(l,mid,x,y);
        if(x > mid)      return son[]->GetSum(mid + ,r,x,y);
        int left = son[]->GetSum(l,mid,x,mid);
        int right = son[]->GetSum(mid + ,r,mid + ,y);
        return left + right;
    }
    int GetMax(int l,int r,int x,int y) {
        if(this == nil) return ;
        if(l == x && y == r)    return _max;
        int mid = (l + r) >> ;
        if(y <= mid) return son[]->GetMax(l,mid,x,y);
        if(x > mid)      return son[]->GetMax(mid + ,r,x,y);
        int left = son[]->GetMax(l,mid,x,mid);
        int right = son[]->GetMax(mid + ,r,mid + ,y);
        return max(left,right);
    }
}none,*root[MAX];

int points,asks;
int head[MAX],total;
int _next[MAX << ],aim[MAX << ];

inline void Add(int x,int y)
{
    _next[++total] = head[x];
    aim[total] = y;
    head[x] = total;
}

int p[MAX],belief[MAX];

int size[MAX],son[MAX],father[MAX],deep[MAX];
int top[MAX],pos[MAX],cnt;

void PreDFS(int x,int last)
{
    deep[x] = deep[last] + ;
    father[x] = last;
    size[x] = ;
    int max_size = ;
    for(int i = head[x]; i; i = _next[i]) {
        if(aim[i] == last)  continue;
        PreDFS(aim[i],x);
        size[x] += size[aim[i]];
        if(size[aim[i]] > max_size)
            max_size = size[aim[i]],son[x] = aim[i];
    }
}

void DFS(int x,int last,int _top)
{
    pos[x] = ++cnt;
    top[x] = _top;
    if(son[x])  DFS(son[x],x,_top);
    for(int i = head[x]; i; i = _next[i]) {
        if(aim[i] == last || aim[i] == son[x])  continue;
        DFS(aim[i],x,aim[i]);
    }
}

inline int GetSum(int x,int y,int p)
{
    int re = ;
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]])  swap(x,y);
        re += root[p]->GetSum(,points,pos[top[x]],pos[x]);
        x = father[top[x]];
    }
    if(deep[x] < deep[y])    swap(x,y);
    re += root[p]->GetSum(,points,pos[y],pos[x]);
    return re;
}

inline int GetMax(int x,int y,int p)
{
    int re = ;
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]])  swap(x,y);
        re = max(re,root[p]->GetMax(,points,pos[top[x]],pos[x]));
        x = father[top[x]];
    }
    if(deep[x] < deep[y])    swap(x,y);
    re = max(re,root[p]->GetMax(,points,pos[y],pos[x]));
    return re;
}

char s[];

int main()
{

    nil = &none;

    cin >> points >> asks;
    for(int i = ; i < MAX; ++i)
        root[i] = new SegTree();
    for(int i = ; i <= points; ++i)
        scanf("%d%d",&p[i],&belief[i]);
    for(int x,y,i = ; i < points; ++i) {
        scanf("%d%d",&x,&y);
        Add(x,y),Add(y,x);
    }
    PreDFS(,);
    DFS(,,);
    for(int i = ; i <= points; ++i)
        root[belief[i]]->Modify(,points,pos[i],p[i]);
    for(int x,y,i = ; i <= asks; ++i) {
        scanf("%s%d%d",s,&x,&y);
        if(s[] == 'C' && s[] == 'C') {
            root[belief[x]]->Modify(,points,pos[x],);
            root[belief[x] = y]->Modify(,points,pos[x],p[x]);
        }
        else if(s[] == 'C' && s[] == 'W')
            root[belief[x]]->Modify(,points,pos[x],p[x] = y);
        else if(s[] == 'Q' && s[] == 'S')
            printf("%d\n",GetSum(x,y,belief[x]));
        else
            printf("%d\n",GetMax(x,y,belief[x]));
    }
    return ;
}