【HackerRank】【HourRank 20】Birjik and Nicole's Tree Game

題目大意

　　給你一棵形态确定的 N 個點的有根樹，1号節點為根，有Q個詢問，每次詢問如果把給定的 k 個點染色，子樹中被染色節點數為0,1,2,...,k的節點分别有多少。

　　 N,Q≤3×105,∑k≤3×105

Solution

　　果然是好久沒打題了，看了題目又不會做。

　　觀察題目可以發現，由于 ∑k≤3×105 ，是以應該把關注的重點放在每次染色的 k 個點上。注意到從下到上，每次子樹中染色數發生變化時，都是目前點位于某些被染色節點的LCA處。是以我們隻要把所有節點的LCA取出重建立樹即可計算答案。

　　這樣的節點有多少個？k2?如果我們用dfs序表示出這顆樹，我們可以發現當所有染色點按照dfs序的時間戳排序後，相鄰兩個的LCA全部拿出後可以發現正好就是所有可能的LCA。我們可以簡單證明一下：

　　考慮排序後被染色的點 ai ， aj （ i≠j ）

　　1. |i−j|=1 時，已經被計算過，加入了答案；

　　2. |i−j|>1 時，不妨設 i<j ，那麼根據定義隻會出現如下情況：

　　　　a） ai 是LCA，此時所有節點 ak(i<k<j) 均在 ai 某個和 aj 相同的子樹中，那麼 ai 和 ai+1 的LCA就是 ai ；

　　　　b） ai 和 aj 在它們的LCA aLCA 的兩個不同子樹中，那麼當 i≤k<j 時，必然存在某個 k 使得ak和 ak+1 在 aLCA 的兩個不同子樹中（否則它們均和 ai 在 aLCA 的相同子樹中），那麼這時 ak 和 ak+1 的LCA即為 aLCA .

　　是以我們最多有 2k 個節點，通過它們按照原樹的父子關系建立新樹即可，點權為子樹中被染色節點數，邊權為兩點原樹間距離。

　　這樣我們就可以在 O((n+∑k)logn) 内完成。

　　

　　

#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<vector>
#include<cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
#define debug(x) {cout<<(#x)<<" "<<x<<endl;}
using namespace std;
typedef long long LL;

inline int read() {
    int x=,f=; char ch=getchar();
    while (!(ch>='0'&&ch<='9')) {if (ch=='-')f=-;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*+(ch-'0'); ch=getchar();}
    return x*f;
}

const int N = ;

int n,q,k,ind=;
vector<int> e[N],e2[N];
int dep[N],f[N][];
int inp[N],oup[N];

inline void dfs(int x,int fa) {
    inp[x]=++ind; dep[x]=dep[fa]+; f[x][]=fa;
    rep(i,,) f[x][i]=f[f[x][i-]][i-];
    for (int i=;i<(int)e[x].size();i++) if (e[x][i]!=fa) dfs(e[x][i],x);
    oup[x]=++ind;
}

inline int LCA(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    per(i,,) if (d&(<<i)) u=f[u][i];
    per(i,,) if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    if (u==v) return u;
    return f[u][];
}

int cnt[N],num[N];

inline void dfs2(int x,int fa) {
    for (int i=;i<(int)e2[x].size();i++) {
        dfs2(e2[x][i],x); num[x]+=num[e2[x][i]];
    }
    cnt[num[x]]+=dep[x]-dep[fa];
}

int ver[N<<];
bool cmp(int a,int b) {
    return inp[a]<inp[b];
}

int stk[N];

int main() {

    #ifndef ONLINE_JUDGE
    //  freopen("input43.txt","r",stdin);
    //  freopen("data.out","w",stdout);
    #endif

    n=read(); rep(i,,n-) {int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u);} 
    dep[]=; dfs(,); 
    q=read();
    while (q--) {
        int k=read();
        int vsize=;
        rep(i,,k) {
            int x=read(); ver[++vsize]=x;
            num[x]=;
        }
        sort(ver+,ver+vsize+,cmp);
        per(i,vsize,) ver[++vsize]=LCA(ver[i],ver[i-]);
        ver[++vsize]=; sort(ver+,ver+vsize+,cmp);
        int nsize=; rep(i,,vsize) if (ver[i]!=ver[i-]) ver[++nsize]=ver[i];
        vsize=nsize;
        int top=; stk[++top]=ver[];
        rep(i,,vsize) {
            while (top>&&oup[stk[top]]<=inp[ver[i]]) top--;
            stk[++top]=ver[i];
            e2[stk[top-]].push_back(stk[top]);
        }
        rep(i,,k) cnt[i]=;
        dfs2(,);  cnt[]=n; rep(i,,k) cnt[]-=cnt[i];
        rep(i,,k) printf("%d ",cnt[i]); puts("");
        rep(i,,vsize) {e2[ver[i]].clear(); num[ver[i]]=;}
    }

    return ;
}