洛谷P4312 [COCI 2009] OTOCI / 極地旅行社(link-cut-tree)

題目描述

不久之前，Mirko建立了一個旅行社，名叫“極地之夢”。這家旅行社在北極附近購買了N座冰島，并且提供觀光服務。

當地最受歡迎的當然是帝企鵝了，這些小家夥經常成群結隊的遊走在各個冰島之間。Mirko的旅行社遭受一次重大打擊，以至于觀光遊輪已經不劃算了。旅行社将在冰島之間建造大橋，并用觀光巴士來運載遊客。

Mirko希望開發一個電腦程式來管理這些大橋的建造過程，以免有不可預料的錯誤發生。這些冰島從1到N标号。一開始時這些島嶼沒有大橋連接配接，并且所有島上的帝企鵝數量都是知道的。每座島上的企鵝數量雖然會有所改變，但是始終在[0, 1000]之間。你的程式需要處理以下三種指令：

1. bridge A B：詢問結點A與結點B是否連通。如果是則輸出“no”。否則輸出“yes”，并且在結點A和結點B之間連一條無向邊。
2. penguins A X：将結點A對應的權值wA修改為X。
3. excursion A B：如果結點A和結點B不連通，則輸出“impossible”。否則輸出結點A到結點B的路徑上的點對應的權值的和。

給出q個操作，要求線上處理所有操作。

輸入輸出格式

輸入格式：

第一行包含一個整數n(1<=n<=30000)，表示節點的數目。

第二行包含n個整數，第i個整數表示第i個節點初始時對應的權值。

第三行包含一個整數q(1<=n<=300000)，表示操作的數目。

以下q行，每行包含一個操作，操作的類别見題目描述。

任意時刻每個節點對應的權值都是1到1000的整數。

輸出格式：

輸出所有bridge操作和excursion操作對應的輸出，每個一行。

輸入輸出樣例

輸入樣例#1：

複制

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5      

輸出樣例#1： 複制

4
impossible
yes
6
yes
yes
15
yes
15
16      

說明

資料範圍：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

題解：放學前二十分鐘準備切道水題，結果因為多寫了個puts身敗名裂……

其他沒什麼好說的了，基本和洛谷那道模闆一模一樣

代碼如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 30030
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;

int ch[N][2],f[N],v[N],sum[N],tag[N];

int not_root(int now)
{
    register int x=f[now]; 
    return lson==now||rson==now;
}

int push_up(int x)
{
    sum[x]=sum[lson]+sum[rson]+v[x];
}

int rev(int x)
{
    swap(lson,rson);
    tag[x]^=1;
}

int push_down(int x)
{
    if(tag[x])
    {
        rev(lson);
        rev(rson);
        tag[x]^=1;
    }
}

int rotate(int x)
{
    int y=f[x],z=f[y],kd=ch[y][1]==x,xs=ch[x][!kd];
    if(not_root(y)) ch[z][ch[z][1]==y]=x;
    ch[x][!kd]=y;
    ch[y][kd]=xs;
    if(xs) f[xs]=y;
    f[y]=x;
    f[x]=z;
    push_up(y);
}

int push_all(int x)
{
    if(not_root(x)) push_all(f[x]);
    push_down(x);
}

int splay(int x)
{
    int y,z;
    push_all(x);
    while(not_root(x))
    {
        y=f[x],z=f[y];
        if(not_root(y)) (ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    push_up(x);
}

int access(int x)
{
    for(int y=0;x;y=x,x=f[x])
    {
        splay(x);
        rson=y;
        push_up(x);
    }
}

int make_root(int x)
{
    access(x);splay(x);
    rev(x);
}

int split(int x,int y)
{
    make_root(x);
    access(y);splay(y);
}

int find_root(int x)
{
    access(x);splay(x);
    while(lson)
    {
        push_down(x);
        x=lson;
    }
    return x;
}

int link(int x,int y)
{
    make_root(x);
    if(find_root(y)==x) return 0;
    f[x]=y;
    return 1;
}

int cut(int x,int y)
{
    make_root(x);
    if(find_root(y)!=x||f[x]!=y||rson) return 0;
    f[x]=ch[y][0]=0;
    return 1;
}

int n,m;
char op[30];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    scanf("%d",&m);
    int from,to;
    while(m--)
    {
        scanf("%s",op);
        puts("");
        if(op[0]=='e')
        {
            scanf("%d%d",&from,&to);
            make_root(from);
            if(find_root(to)!=from)
            {
                puts("impossible");
                continue;
            }
            printf("%d\n",sum[to]);
        }
        if(op[0]=='p')
        {
            scanf("%d%d",&from,&to);
            splay(from);
            v[from]=to;
        }
        if(op[0]=='b')
        {
            scanf("%d%d",&from,&to);
            if(link(from,to)) puts("yes");
            else puts("no");
        }
    }
}