HNOI2014 世界树

题目:

  世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。
  世界树的形态可以用一个数学模型来描述:世界树中有 个种族,种族的编号分别从 ,分别生活在编号为 的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为 。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地 之间有道路, 之间有道路,因为每条道路长度为 而且又不可能出现环,所以 之间的距离为
  出于对公平的考虑,第 年,世界树的国王需要授权 个种族的聚居地为临时议事处。对于某个种族 为种族的编号),如果距离该种族最近的临时议事处为 为议事处所在聚居地的编号),则种族 将接受 议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则 为其中编号最小的临时议事处)。
  现在国王想知道,在 年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

思路:

  每次查询原树中一部分的点,比较常见的思路是建虚树吧。
  建出虚树后,虚树上的每条边就对应了原树的一条链(包括链上的旁支),每次考虑每条虚树上的边(也就是原树上的链)上的点的分配。
  显然这些点肯定是被分成上下两段,设这段链为 ,下面一段肯定属于 子树中离 最近的临时议事处,上面一段属于距离 最近的点(如果最近是 就是次近),如果知道了这两个点到 的距离,用在倍增数组上二分一下就能找到断点了。
  求最近的点可以做两次树形dp,记录子树内最大次大,子树外最大即可。复杂度

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;
const int N = 300005;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
Link<N, N * 2, int> G, T;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

int fa[N][20], dfn[N], cur, dep[N], sz[N], en[N];
void dfs_init(int o, int f) {
    fa[o][0] = f; dfn[o] = ++cur; sz[o] = 1;
    dep[o] = dep[f] + 1;
    erep(k, G, o) {
        int v = G[k];
        if(v == f) continue;
        dfs_init(v, o);
        sz[o] += sz[v];
    }
    en[o] = cur;
}
void init(int n) {
    dfs_init(n, 0);
    rep(k, 1, 18)
        rep(i, 1, n) 
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
}

int vec[N * 2], stk[N];
bool mark[N];
bool cmp_dfn(int x, int y) {
    return dfn[x] < dfn[y];
}
struct Data {
    int dis, id;
    Data operator+ (const int d) {
        return (Data) {dis + d, id};
    }
    bool operator< (const Data d) const {
        if(dis == d.dis) return id < d.id;
        return dis < d.dis;
    }
} dis[N][3];
void dfs_dis1(int o, int f) {
    dis[o][0] = (Data) {mark[o] ? 0 : (int) 1e9, o};
    dis[o][1] = (Data) {(int) 1e9, 0};
    erep(k, T, o) {
        int v = T[k];
        if(v == f) continue;
        dfs_dis1(v, o);
        tomin(dis[o][1], dis[v][0] + (dep[v] - dep[o]));
        if(dis[o][1] < dis[o][0]) swap(dis[o][1], dis[o][0]);
    }
}
void dfs_dis2(int o, int f, Data d) {
    if(mark[o]) d = (Data) {0, o};
    dis[o][2] = d;
    Data mn = d, smn = (Data) {(int) 1e9, 0};
    erep(k, T, o) {
        int v = T[k];
        if(v == f) continue;
        tomin(smn, dis[v][0] + (dep[v] - dep[o]));
        if(smn < mn) swap(mn, smn);
    }
    erep(k, T, o) {
        int v = T[k];
        if(v == f) continue;
        dfs_dis2(v, o, ((v == mn.id) ? smn : mn) + (dep[v] - dep[o]));
    }
}
int get_son(int v, int o) {
    drep(i, 18, 0) 
        if(dep[fa[v][i]] > dep[o]) 
            v = fa[v][i];
    return v;
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    rep(i, 0, 18) if(d >> i & 1) u = fa[u][i];
    if(u == v) return u;
    drep(i, 18, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
int ans[N];
void dfs_calc(int o, int f) {
    int now = sz[o];
    erep(k, T, o) {
        int v = T[k];
        if(v == f) continue;
        int u = v;
        int p = get_son(v, o);
        Data d = min(dis[o][2], (dis[o][0].id == v) ? dis[o][1] : dis[o][0]);
        drep(i, 18, 0) {
            int t = fa[u][i];
            if(dep[t] <= dep[o]) continue;
            if(dis[v][0] + (dep[v] - dep[t]) < d + (dep[t] - dep[o]))
                u = t;
        }
        now -= sz[p];
        ans[d.id] += sz[p] - sz[u];
        ans[dis[v][0].id] += sz[u] - sz[v];
        dfs_calc(v, o);
    }
    ans[min(dis[o][0], dis[o][2]).id] += now;
}

int b[N];
void query(int m, int n) {
    int tot = m;
    rep(i, 1, m) scanf("%d", vec + i), b[i] = vec[i];
    rep(i, 1, m) mark[b[i]] = true;
    sort(vec + 1, vec + 1 + m, cmp_dfn);
    rep(i, 2, m) vec[++tot] = lca(vec[i - 1], vec[i]);
    sort(vec + 1, vec + 1 + tot, cmp_dfn);
    tot = unique(vec + 1, vec + 1 + tot) - vec - 1;
    int top = 1;
    stk[top] = vec[1];
    rep(i, 2, tot) {
        int o = vec[i];
        while(dfn[o] > en[stk[top]]) top--;
        T.add(stk[top], o); 
        stk[++top] = o;
    }

    dfs_dis1(vec[1], 0); dfs_dis2(vec[1], 0, (Data) {(int) 1e9, 0});
    dfs_calc(vec[1], 0);
    ans[min(dis[vec[1]][0], dis[vec[1]][2]).id] += n - sz[vec[1]];
    rep(i, 1, m) printf("%d%c", ans[b[i]], " \n"[i == m]);

    rep(i, 1, tot) mark[vec[i]] = false, T.HEAD[vec[i]] = 0, ans[vec[i]] = 0;
    T.tot = 0;
}


int main() {
    File(worldtree);
    int n, q, m;
    scanf("%d", &n);
    rep(i, 2, n) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.add(u, v); G.add(v, u);
    }
    init(n);
    scanf("%d", &q);
    while(q--) {
        scanf("%d", &m);
        query(m, n);
    }
    return 0;
}