2012-2013 ACM-ICPC, NEERC, Southern Subregional Contest 解題報告

題目連結

就推薦幾個有營養的題好了

H - Sultan's Pearls

由于最終狀态懸挂在桌面以下的長度始終是不變的，是以可以枚舉最終哪個端點懸挂在最下面，然後二分找到能去掉的最多的開頭的部分

K - Tree Queries Online（SGU 550）

給你一棵樹，每條邊都有一個标号，然後給你一個删邊的順序，每删除一條邊，就要輸出這條邊的邊權，然後數一下目前塊兩邊各有多少個點，給點少的那一半的每條邊都乘上目前邊的邊權，給多的那一半都加上目前邊的邊權。

這一看就是個裸的資料結構題啊，但是，有簡單做法。。。

每次暴力搜尋兩個塊，當一邊無法擴充更多的點的時候就停止，然後點少的那一邊暴力修改每條邊的标記，多的那一邊加個懶惰标記，維護一個delta變量就好了，表示這一塊被加了多少。

說起來簡單，寫起來的時候要相當注意，一不小心就逾時了。往兩邊同時搜的時候要好好設計，邊的通路量可能會很大

每次删除一條邊之後實際上可以用鄰接表删除這條邊，即多記錄一個pre，每次将pre的next指向next

如果使用上述方法要注意這樣的資料，一個點的度數為n-1，其他點的度數都為1，然後順時針或者逆時針删邊。

其實資料還是挺弱的，沒有逆時針删邊的順序，是以加上鄰接表的優化後也沒有塊多少

這題還可以splay，改天再補。

#include <cstdio>
#include <set>
#include <time.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400010;
const int mod = 99990001;
typedef long long lld;
int n;
struct Edge {
    int pre;
    int s, t, w;
    int id, next;
} edge[N * 2];
int head[N];
struct Data {
    int s, t, w;
    Data() {
    }
    Data(int _s, int _t, int _w) :
    s(_s), t(_t), w(_w) {
    }
} edge_src[N];
int E, Btype, Belong[N], ADD[N], cur[N];
void add_edge(int a, int b, int w, int id) {
    edge[E].s = a;
    edge[E].t = b;
    edge[E].id = id;
    edge[E].next = head[a];
    if (head[a] != -1)
        edge[head[a]].pre = E;
    head[a] = E;
    cur[a] = E++;
}
void init() {
    Btype = 1;
    E = 0;
    memset(cur, -1, sizeof(cur));
    memset(head, -1, sizeof(head));
}
int Q[N], q[N];
int he1, ta1;
int he2, ta2;
int ss, tt;
int DFN;
bool vis[N];
int MI_1, MI_2;
int rec[N];
int T,T1,T2;
int QQQ[N],Tot_Q;
void destroy() { // update vis[]
    for(int i = 1; i <= Tot_Q; i++) {
        vis[QQQ[i]]=false;
        cur[QQQ[i]]  = head[QQQ[i]];
    }
}
int another;
void split_set(int s, int wi) {
    int ori = Belong[another];
    Belong[s] = ++Btype;
    ADD[Btype] = 0;
    int he = 0, ta = 0;
    rec[++ta] = s;
    while (he < ta) {
        int now = rec[++he];
        Belong[now] = Btype;
        vis[now] = false;
        for (int i = head[now]; i != -1; i = edge[i].next) {
            T2++;
            int v = edge[i].t;
            if (v == another)
                continue;
            if (vis[v]) {
                int id = edge[i].id;
                if (ADD[ori]) {
                    edge_src[id].w += ADD[ori];
                    if (edge_src[id].w >= mod)
                        edge_src[id].w -= mod;
                }
                lld tmp = (lld) edge_src[id].w * wi;
                if (tmp >= mod)
                    tmp %= mod;
                edge_src[id].w = tmp;
                rec[++ta] = v;
            }
        }
    }
    ADD[ori] += wi;
    if (ADD[ori] >= mod)
        ADD[ori] -= mod;
}
void split(int s, int t, int wi, int id) {
    MI_1 = MI_2 = 1000000;
    DFN = Belong[s];
    he1 = ta1 = he2 = ta2 = 0;
    Q[++ta1] = s;
    q[++ta2] = t;
    vis[s] = vis[t] = true;
    Tot_Q = 0;
    while (true) {

        bool f1 = false;
        while (he1 < ta1) {
            int now = Q[he1 + 1];
            if (now < MI_1)
                MI_1 = now;
            for (int i = cur[now]; i != -1; i = edge[i].next) {
                T++;
                int v = edge[i].t;
                if (Belong[v] == DFN && !vis[v]) {
                    vis[v] = true;
                    QQQ[++Tot_Q] = v;
                    Q[++ta1] = v;
                    cur[now] = edge[i].next;
                    f1 = true;
                    break;
                }
            }
            if (f1)
                break;
            cur[now] = head[now];
            ++he1;
        }
        bool f2 = false;
        while (he2<ta2) {
            int now = q[he2 + 1];
            if (now < MI_2)
                MI_2 = now;
            for (int i = cur[now]; i != -1; i = edge[i].next) {
                T++;
                int v = edge[i].t;
                if (Belong[v] == DFN && !vis[v]) {
                    vis[v] = true;
                    QQQ[++Tot_Q] = v;
                    q[++ta2] = v;
                    cur[now] = edge[i].next;
                    f2 = true;
                    break;
                }
            }
            if (f2)
                break;
            cur[now] = head[now];
            ++he2;
        }

        if (!f1 && !f2) {
            if (MI_1 < MI_2) {
                another = t;
                split_set(s, wi);
            } else {
                another = s;
                split_set(t, wi);
            }
        } else if (!f1) {
            another = t;
            split_set(s, wi);
        } else if (!f2) {
            another = s;
            split_set(t, wi);
        }
        if (!f1 || !f2) {
            vis[s] = vis[t] = false;
            cur[s] = head[s];
            cur[t] = head[t];
            destroy();
            break;
        }
    }
}
int main() {
//Reopen("a.txt", "r", stdin);
//freopen("b.txt","w",stdout);
    int a, b, w, id;
    init();
    scanf("%d", &n);
    double start = clock();
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &a, &b, &w);
        add_edge(a, b, w, i);
        add_edge(b, a, w, i);
        edge_src[i] = Data(a, b, w);
    }
    for (int i = 1; i <= n; i++)
        Belong[i] = 1;
    for (int i = 1; i < n; i++) {
        scanf("%d", &id);
        int s = edge_src[id].s;
        int t = edge_src[id].t;
        int w = edge_src[id].w;
        printf("%d\n",(w + ADD[Belong[s]]) % mod);
        fflush(stdout);
        split(s, t, (w + ADD[Belong[s]]) % mod, id);
        int ed1 = (id - 1) * 2;
       if (head[s] == ed1) {
            head[s] = edge[head[s]].next;
            cur[s] = head[s];
        } else {
            edge[edge[ed1].pre].next = edge[ed1].next;
            if(~edge[ed1].next)edge[edge[ed1].next].pre = edge[ed1].pre;
        }
        int ed2 =  (id - 1) * 2 + 1;
        if (head[t] == ed2) {
            head[t] = edge[head[t]].next;
            cur[t] = head[t];
        } else {
            edge[edge[ed2].pre].next = edge[ed2].next;
            if(~edge[ed2].next)edge[edge[ed2].next].pre = edge[ed2].pre;
        }
    }
    return 0;
}