題目

世界樹是一棵無比巨大的樹，它伸出的枝干構(gòu)成了整個世界。在這里，生存著各種各樣的種族和生靈，他們共同信奉著絕對公正公平的女神艾莉森，在他們的信條里，公平是使世界樹能夠生生不息、持續(xù)運轉(zhuǎn)的根本基石。
世界樹的形態(tài)可以用一個數(shù)學模型來描述：世界樹中有n個種族，種族的編號分別從1到n，分別生活在編號為1到n的聚居地上，種族的編號與其聚居地的編號相同。有的聚居地之間有雙向的道路相連，道路的長度為1。保證連接的方式會形成一棵樹結(jié)構(gòu)，即所有的聚居地之間可以互相到達，并且不會出現(xiàn)環(huán)。定義兩個聚居地之間的距離為連接他們的道路的長度；例如，若聚居地a和b之間有道路，b和c之間有道路，因為每條道路長度為1而且又不可能出現(xiàn)環(huán)，所臥a與c之間的距離為2。
出于對公平的考慮，第i年，世界樹的國王需要授權(quán)m[i]個種族的聚居地為臨時議事處。對于某個種族x（x為種族的編號），如果距離該種族最近的臨時議事處為y（y為議事處所在聚居地的編號），則種族x將接受y議事處的管轄（如果有多個臨時議事處到該聚居地的距離一樣，則y為其中編號最小的臨時議事處）。
現(xiàn)在國王想知道，在q年的時間里，每一年完成授權(quán)后，當年每個臨時議事處將會管理多少個種族（議事處所在的聚居地也將接受該議事處管理）。 現(xiàn)在這個任務(wù)交給了以智慧著稱的靈長類的你：程序猿。請幫國王完成這個任務(wù)吧。

輸入格式

第一行為一個正整數(shù)n，表示世界樹中種族的個數(shù)。
接下來n-l行，每行兩個正整數(shù)x，y，表示x聚居地與y聚居地之間有一條長度為1的雙
向道路。接下來一行為一個正整數(shù)q，表示國王詢問的年數(shù)。
接下來q塊，每塊兩行：
第i塊的第一行為1個正整數(shù)m[i]，表示第i年授權(quán)的臨時議事處的個數(shù)。
第i塊的第二行為m[i]個正整數(shù)h[l]、h[2]、…、h[m[i]]，表示被授權(quán)為臨時議事處的聚居地編號（保證互不相同）。

輸出格式

輸出包含q行，第i行為m[i]個整數(shù)，該行的第j(j=1，2…，，m[i])個數(shù)表示第i年被授權(quán)的聚居地h[j]的臨時議事處管理的種族個數(shù)。

輸入樣例

10

2 1

3 2

4 3

5 4

6 1

7 3

8 3

9 4

10 1

5

2

6 1

5

2 7 3 6 9

1

8

4

8 7 10 3

5

2 9 3 5 8

輸出樣例

1 9

3 1 4 1 1

10

1 1 3 5

4 1 3 1 1

提示

N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000

題解

我代碼能力真是太弱了

按套路先建虛樹，然后在樹上統(tǒng)計答案

過程比較煩：
①先求出虛樹上每個點最近的議事處
兩遍dfs即可，第一遍dfs用兒子最近的議事處更新父親，第二遍dfs用父親更新兒子，因為可能會出現(xiàn)兒子經(jīng)過父親到達另一個兒子的情況

②對于虛樹上的每條邊，計算貢獻
由于邊上有很多非虛樹點，設(shè)邊為(u,v)，其中u為父親，那么用son[u]的子樹大小減去v的子樹大小就是之間的點數(shù)
如果u和v最近的議事處一樣，那么這些點都加入那個議事處
如果不一樣，那么在這條邊上找出分界點，分別貢獻到兩個議事處
其中son[u]和分界點在樹上倍增找出

③有些點既不在虛樹邊上，也不在虛樹上
我們記g[u]為u點在已被計算的子樹節(jié)點數(shù)量，那么剩余的節(jié)點數(shù)就可以加到u最近的議事處中
g[u]可以用②中son[u]的子樹大小累加

然后就開碼吧- -

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define LL long long int #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts(""); using namespace std; const int maxn = 300005,maxm = 600005,INF = 1000000000; inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag; } int hh[maxn],nn = 2; int h[maxn],ne = 2; struct EDGE{int from,to,nxt,w;}e[maxm],ed[maxm]; inline void add(int u,int v){e[nn] = (EDGE){u,v,hh[u],0}; hh[u] = nn++;e[nn] = (EDGE){v,u,hh[v],0}; hh[v] = nn++; } inline void build(int u,int v,int w){if (!w) return;ed[ne] = (EDGE){u,v,h[u],w}; h[u] = ne++;ed[ne] = (EDGE){v,u,h[v],w}; h[v] = ne++; } int n; int fa[maxn][20],dep[maxn],dfn[maxn],siz[maxn],cnt; void dfs(int u){dfn[u] = ++cnt;siz[u] = 1;for (int i = 1; i <= 19; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];for (int k = hh[u],to; k; k = e[k].nxt)if ((to = e[k].to) != fa[u][0]){fa[to][0] = u; dep[to] = dep[u] + 1;dfs(to);siz[u] += siz[to];} } int lca(int u,int v){if (dep[u] < dep[v]) swap(u,v);for (int i = 0,d = dep[u] - dep[v]; (1 << i) <= d; i++)if ((1 << i) & d) u = fa[u][i];if (u == v) return u;for (int i = 19; i >= 0; i--)if (fa[u][i] != fa[v][i]){u = fa[u][i];v = fa[v][i];}return fa[u][0]; } int K,a[maxn],st[maxn],top; inline bool cmp(const int& a,const int& b){return dfn[a] < dfn[b]; } void rebuild(){st[top = 1] = 1; ne = 2;sort(a + 1,a + 1 + K,cmp);for (int i = 1; i <= K; i++){int u = a[i],p = lca(u,st[top]);if (p == st[top]){st[++top] = u; continue;}else {while (true){if (dep[p] >= dep[st[top - 1]]){build(p,st[top],dep[st[top]] - dep[p]);top--;st[++top] = p;break;}build(st[top - 1],st[top],dep[st[top]] - dep[st[top - 1]]);top--;}st[++top] = u;}}while (top > 1)build(st[top - 1],st[top],dep[st[top]] - dep[st[top - 1]]),top--; } int id[maxn]; int nr[maxn],nd[maxn]; int ans[maxn],g[maxn]; int b[maxn],tot; void dfs1(int u,int f){if (id[u]){nr[u] = u;nd[u] = 0;}else {nd[u] = INF;}Redge(u) if ((to = ed[k].to) != f){dfs1(to,u);if (nd[to] + ed[k].w < nd[u] || (nd[to] + ed[k].w == nd[u] && nr[to] < nr[u])){nd[u] = nd[to] + ed[k].w;nr[u] = nr[to];}} } void dfs2(int u,int f){Redge(u) if ((to = ed[k].to) != f){if (nd[u] + ed[k].w < nd[to] || (nd[u] + ed[k].w == nd[to] && nr[to] > nr[u])){nd[to] = nd[u] + ed[k].w;nr[to] = nr[u];}dfs2(to,u);}h[u] = 0; g[u] = 0;b[++tot] = u; } int up(int u,int dis){for (int i = 0; (1 << i) <= dis; i++)if ((1 << i) & dis) u = fa[u][i];return u; } void cal(){for (int k = 2; k < ne; k += 2){int x = ed[k].from,y = ed[k].to;int D = nd[x] - nd[y],nds = ed[k].w - 1;int s = up(y,nds);g[x] += siz[s];if (nr[x] == nr[y]){ans[id[nr[x]]] += siz[s] - siz[y];continue;}if (D >= nds){ans[id[nr[y]]] += siz[s] - siz[y];}else if (-D >= nds){ans[id[nr[x]]] += siz[s] - siz[y];}else {if (D > 0){int ns = nds - D;int dis = D + (ns >> 1) + ((ns & 1) && nr[y] < nr[x]);int mid = up(y,dis);ans[id[nr[y]]] += siz[mid] - siz[y];ans[id[nr[x]]] += siz[s] - siz[mid];}else {int ns = nds + D;int dis = (ns >> 1) + ((ns & 1) && nr[y] < nr[x]);int mid = up(y,dis);ans[id[nr[y]]] += siz[mid] - siz[y];ans[id[nr[x]]] += siz[s] - siz[mid];}}}for (int i = 1; i <= tot; i++)ans[id[nr[b[i]]]] += siz[b[i]] - g[b[i]]; } void Solve(){tot = 0;dfs1(1,0);dfs2(1,0);cal();for (int i = 1; i <= K; i++) printf("%d ",ans[i]); puts("");for (int i = 1; i <= K; i++) id[a[i]] = ans[i] = 0; } int main(){n = read();for (int i = 1; i < n; i++) add(read(),read());dfs(1);int q = read();while (q--){K = read();for (int i = 1; i <= K; i++){a[i] = read();id[a[i]] = i;}rebuild();Solve();}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/8672388.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3572 [Hnoi2014]世界树 【虚树 + 树形dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。