題解: 首先建出一顆虛樹? 對于虛樹上的每個節點DP找出離得最近的關鍵節點的編號和距離 然后考慮一遍dfs 對于每條鏈上子樹 我們倍增找到mid位置 然后mid以下的屬于下面節點 mid以上的屬于上面的節點 維護即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
const int inf=1e9;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,q,k;
int p[MAXN],cnt,num[MAXN],dep[MAXN],f[MAXN][21];
vector<int>vec[MAXN],v1,v2;
bool cmp(int aa,int bb){return p[aa]<p[bb];}
void dfs(int x,int pre,int deep){num[x]=1;dep[x]=deep+1;p[x]=++cnt;f[x][0]=pre;link(x){if(j->t!=pre)dfs(j->t,x,deep+1),num[x]+=num[j->t];}
}
void dfs1(int x){inc(i,1,20)f[x][i]=f[f[x][i-1]][i-1];link(x){if(j->t!=f[x][0])dfs1(j->t);}
}
int Lca(int u,int v){if(dep[u]<dep[v])swap(u,v);int tmp=dep[u]-dep[v];for(int i=0;i<=20;i++)if(tmp&(1<<i))u=f[u][i];if(u==v)return u;for(int i=20;i>=0;i--){if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];}return f[u][0];
}
int st[MAXN],tot;
int dist[MAXN],pos[MAXN],ans[MAXN],vis[MAXN];
void built(int x){v2.pb(x);if(!tot){st[++tot]=x;dist[x]=inf;pos[x]=x;return ;}int lca=Lca(x,st[tot]);while(tot>1&&dep[st[tot-1]]>dep[lca]){vec[st[tot]].pb(st[tot-1]);vec[st[tot-1]].pb(st[tot]);tot--;}if(dep[st[tot]]>dep[lca]){vec[st[tot]].pb(lca);vec[lca].pb(st[tot]);v2.pb(lca);dist[lca]=inf;pos[lca]=lca;tot--;}if(!tot||dep[lca]>dep[st[tot]])st[++tot]=lca;st[++tot]=x;
}
int Dis(int u,int v){int lca=Lca(u,v);return dep[u]+dep[v]-2*dep[lca];
}
void dfs2(int x,int pre){for(int i=0;i<vec[x].size();i++){if(vec[x][i]!=pre){int dis=Dis(vec[x][i],x);if(dist[vec[x][i]]>dist[x]+dis)dist[vec[x][i]]=dist[x]+dis,pos[vec[x][i]]=pos[x];else if(dist[vec[x][i]]==dist[x]+dis)pos[vec[x][i]]=min(pos[x],pos[vec[x][i]]);dfs2(vec[x][i],x);if(dist[vec[x][i]]+dis<dist[x])dist[x]=dist[vec[x][i]]+dis,pos[x]=pos[vec[x][i]];else if(dist[vec[x][i]]+dis==dist[x])pos[x]=min(pos[x],pos[vec[x][i]]);			}}
}
int find1(int u,int x){if(x==0)return u;for(int i=0;i<=20;i++)if(x&(1<<i))u=f[u][i];return u;
}
void dfs3(int x,int pre){ans[pos[x]]+=num[x];for(int i=0;i<vec[x].size();i++){if(vec[x][i]!=pre){ans[pos[x]]-=num[vec[x][i]];if(pos[x]!=pos[vec[x][i]]&&dep[vec[x][i]]-dep[x]>1){int t2=dist[x]+dep[vec[x][i]]-dep[x]-dist[vec[x][i]];int t1=(dist[x]+dep[vec[x][i]]-dep[x]-dist[vec[x][i]])/2;if(t2%2==0){if(pos[x]<pos[vec[x][i]])t1--;}t1=find1(vec[x][i],t1);ans[pos[vec[x][i]]]+=num[t1]-num[vec[x][i]];ans[pos[x]]-=(num[t1]-num[vec[x][i]]);}dfs3(vec[x][i],x);}}
}
int main(){n=read();int u,v;inc(i,1,n-1)u=read(),v=read(),add(u,v),add(v,u);dfs(1,0,0);dfs1(1);q=read();while(q--){k=read();v1.clear();v2.clear();inc(i,1,k)u=read(),v1.pb(u),vis[i]=u;tot=0;sort(v1.begin(),v1.end(),cmp);inc(i,1,k)built(v1[i-1]);while(tot>1){vec[st[tot-1]].pb(st[tot]);vec[st[tot]].pb(st[tot-1]);tot--;}inc(i,1,k)dist[v1[i-1]]=0,pos[v1[i-1]]=v1[i-1];if(st[1]!=1){vec[1].pb(st[1]);vec[st[1]].pb(1);dist[1]=inf;pos[1]=1;v2.pb(1);}dfs2(v1[0],0);dfs2(v1[0],0);dfs3(1,0);inc(i,1,k)printf("%d ",ans[vis[i]]);printf("\n");for(int i=0;i<v2.size();i++)vec[v2[i]].clear(),ans[v2[i]]=0;}
}

　

3572: [Hnoi2014]世界樹

Time Limit:?20 Sec??Memory Limit:?512 MB
Submit:?2337??Solved:?1269
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

1 9
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1

HINT

?

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

轉載于:https://www.cnblogs.com/wang9897/p/9670394.html

總結

以上是生活随笔為你收集整理的BZOJ3572: [Hnoi2014]世界树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。