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;
}