latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年11月21日 星期六

[ sphere online judge ] SPOJ QTREE - Query on a tree 使用 link-cut tree

題目:
http://www.spoj.com/problems/QTREE/

解法:
這題可以用除了link-cut tree以外的方法來做,速度也會比較快,但是最近在研究link-cut tree,所以就試著用link-cut tree解了。
首先,對於題目給的樹,利用BFS將每個點設成單獨一個樹鏈(之後再access操作的時候就會連起來了,不用擔心),並每個點都記錄連到父母那條邊的權重,用edge_node陣列記錄每條邊被記錄在哪個點內。因為每個點是紀錄連到父母節點邊的權重,所以不可以有換根的情形發生。修改邊時利用edge_node陣列把要修改的點找出來然後直接修改,查詢則在access的過程中完成。
記住這題node不可以用vector來做,會TLE不知道為什麼

code:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
struct splay_tree{
    int ch[2],pa;
    int data,ma;
    splay_tree():pa(0),data(0x80000000),ma(0x80000000){ch[0]=ch[1]=0;}
}node[10005];
inline bool isroot(int x){
    return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x;
}
inline void up(int x){
    node[x].ma=node[x].data;
    if(node[x].ch[0])node[x].ma=max(node[node[x].ch[0]].ma,node[x].ma);
    if(node[x].ch[1])node[x].ma=max(node[node[x].ch[1]].ma,node[x].ma);
}
inline void rotate(int x){
    int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x);
    node[x].pa=z;
    if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x;
    node[y].ch[d]=node[x].ch[d^1];
    node[node[y].ch[d]].pa=y;
    node[y].pa=x,node[x].ch[d^1]=y;
    up(y);
    up(x);
}
inline void splay(int x){
    while(!isroot(x)){
        int y=node[x].pa;
        if(!isroot(y)){
            int z=node[y].pa;
            if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}
inline void access(int x,bool is){
    int last=0;
    while(x){
        splay(x);
        if(!node[x].pa&&is){
            printf("%d\n",max(node[last].ma,node[node[x].ch[1]].ma));
        }
        node[x].ch[1]=last;
        up(x);
        last=x;
        x=node[x].pa;
    }
}
struct EDGE{
    int a,b,c;
}e[10005];
int n;
vector<pair<int ,int > >G[10005];
int pa[10005],edge_node[10005];
inline void bfs(int root){
    std::queue<int > q;
    for(int i=1;i<=n;++i)pa[i]=0;
    q.push(root);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<(int)G[u].size();++i){
            int v=G[u][i].first;
            if(v!=pa[u]){
                pa[v]=u;
                node[v].pa=u;
                node[v].data=e[G[u][i].second].c;
                edge_node[G[u][i].second]=v;
                up(v);
                q.push(v);
            }
        }
    }
}
char s[10];
int t,a,b;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            G[i].clear();
            node[i].ch[0]=node[i].ch[1]=node[i].pa=0;
            node[i].data=node[i].ma=0x80000000;
        }
        for(int i=1;i<n;++i){
            scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
            G[e[i].a].push_back(make_pair(e[i].b,i));
            G[e[i].b].push_back(make_pair(e[i].a,i));
        }
        bfs(1);
        while(scanf("%s",s)&&s[0]!='D'){
            scanf("%d%d",&a,&b);
            if(s[0]=='C'){
                a=edge_node[a];
                splay(a);
                node[a].data=b;
                up(a);
            }else{
                access(a,0);
                access(b,1);
            }
        }
    }
    return 0;
}

沒有留言:

張貼留言