3572: [Hnoi2014]世界树
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 520 Solved: 300
[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
21
32
43
54
61
73
83
94
10 1
5
2
61
5
27369
1
8
4
87103
5
29358
21
32
43
54
61
73
83
94
10 1
5
2
61
5
27369
1
8
4
87103
5
29358
Sample Output
19
31411
10
1135
41311
31411
10
1135
41311
只要知道虚树这个东西，其实这道题的解法还是很容易想到的，由于建了虚树后一条边最多被分成两部分，分界点离两点距离相等，可以用树形DP解决。
因此本题难点在于如何建虚树。我的做法是将所有点按照dfs序排序，依次加点，通过一个栈维护最右边的链。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
#define MAXN 602100
#define MAXE MAXN*2
#define MAXV MAXN
#define INF 0x3f3f3f3f
int n,m;
struct Edge
{
int np;
Edge *next;
}*V[MAXV],E[MAXE];
int tope=-;
void addedge(int x,int y)
{
E[++tope].np=y;
E[tope].next=V[x];
V[x]=&E[tope];
}
int q[MAXN];
int pnt[MAXN];
int depth[MAXN];
int siz[MAXN];
void bfs(int now)
{
int head=-,tail=;
Edge *ne;
pnt[now]=now;
q[]=now;
while(head<tail)
{
now=q[++head];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
pnt[ne->np]=now;
depth[ne->np]=depth[now]+;
q[++tail]=ne->np;
}
}
for (int i=tail;i>=;i--)
{
now=q[i];
siz[now]=;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
siz[now]+=siz[ne->np];
}
}
}
int jump[][MAXN];
void init_lca()
{
for (int i=;i<=n;i++)
jump[][i]=pnt[i];
for (int j=;j<;j++)
for (int i=;i<=n;i++)
jump[j][i]=jump[j-][jump[j-][i]];
}
int swim(int now,int dep)
{
for (int i=;i<;i++)
if (dep&(<<i))
now=jump[i][now];
return now;
}
int lca(int x,int y)
{
if (depth[x]<depth[y])swap(x,y);
int dep=depth[x]-depth[y];
for (int i=;i<;i++)
if (dep&(<<i))
x=jump[i][x];
if (x==y)return x;
for (int i=;i>=;i--)
if (jump[i][x]!=jump[i][y])
x=jump[i][x],y=jump[i][y];
return pnt[x];
}
int dis(int x,int y)
{
return depth[x]+depth[y]-*depth[lca(x,y)];
}
int stack[MAXN],tops=-;
int pos[MAXN],dfstime;
void dfs(int now)
{
Edge *ne;
stack[++tops]=now;
while (~tops)
{
now=stack[tops--];
pos[now]=++dfstime;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
stack[++tops]=ne->np;
}
}
}
int seq[MAXN];
int tot[MAXN];
struct qur_t
{
int id;
int index;
}ql[MAXN];
bool cmp_pos(qur_t q1,qur_t q2)
{
return pos[q1.index]<pos[q2.index];
}
bool cmp_id(qur_t q1,qur_t q2)
{
return q1.id<q2.id;
}
struct edge
{
int x,y,v;
int dx,dy,gx,gy;
edge(){}
edge(int x,int y,int v):x(x),y(y),v(v){}
};
namespace task2
{
const int maxn=MAXN;
const int maxe=maxn;
const int maxv=maxn*;
struct Edge
{
int np;
int val;
Edge *next;
}E[maxe],*V[maxv];
int tope=-;
void addedge(int x,int y,int z)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope];
}
int q[maxv];
int pnt[maxv];
int fdis[maxv];
pair<int,int> dpson[maxn];
pair<int,int> dppnt[maxn];
bool cent[maxv];
int vsiz[maxv];
void bfs(int rt)
{
int now=rt;
Edge *ne;
int head=-,tail=;
q[]=now;
while (head<tail)
{
now=q[++head];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
pnt[ne->np]=now;
fdis[ne->np]=ne->val;
q[++tail]=ne->np;
}
}
for (int i=tail;i>=;i--)
{
now=q[i];
if (cent[now])
dpson[now]=make_pair(,now);
else
{
dpson[now]=make_pair(INF,INF);
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
dpson[now]=min(dpson[now],make_pair(dpson[ne->np].first+ne->val,dpson[ne->np].second));
}
}
}
dppnt[rt]=dpson[rt];
for (int i=;i<=tail;i++)
{
now=q[i];
if (cent[now])dppnt[now]=make_pair(,now);
pair<int,int> pr=min(dpson[now],dppnt[now]);
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
dppnt[ne->np]=min(dppnt[ne->np],make_pair(pr.first+ne->val,pr.second));
}
}
for (int i=tail;i>=;i--)
{
int now=q[i];
vsiz[now]=siz[now];
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==pnt[now])continue;
vsiz[now]-=siz[swim(ne->np,ne->val-)];
}
}
vsiz[rt]+=n-siz[rt];
}
vector<int> pl;
void main(vector<edge> &el,vector<int> &cl)
{
pl.clear();
for (int i=;i<el.size();i++)
{
addedge(el[i].x,el[i].y,el[i].v);
addedge(el[i].y,el[i].x,el[i].v);
pl.push_back(el[i].x);
pl.push_back(el[i].y);
}
sort(pl.begin(),pl.end());
pl.erase(unique(pl.begin(),pl.end()),pl.end());
int rt=pl[];
for (int i=;i<pl.size();i++)
{
if (depth[rt]>depth[pl[i]])rt=pl[i];
dppnt[pl[i]]=make_pair(INF,INF);
}
for (int i=;i<cl.size();i++)
cent[cl[i]]=true;
bfs(rt);
for (int i=;i<el.size();i++)
{
if (pnt[el[i].y]==el[i].x)
swap(el[i].x,el[i].y);
pair<int,int> prx,pry;
prx=min(dpson[el[i].x],dppnt[el[i].x]);
pry=min(dpson[el[i].y],dppnt[el[i].y]);
if (prx.second==pry.second)
{
el[i].dx=el[i].v;
el[i].gx=prx.second;
el[i].dy=-;
el[i].gy=-;
}else
{
el[i].gx=prx.second;
el[i].gy=pry.second;
el[i].dx=(el[i].v-+pry.first-prx.first)/;
if (el[i].v-+pry.first-prx.first<)el[i].dx--;
if ((el[i].v-+pry.first-prx.first)% && el[i].gx<el[i].gy)
el[i].dx++;
el[i].dy=el[i].v--el[i].dx;
}
}
for (int i=;i<pl.size();i++)
{
V[pl[i]]=;
pnt[pl[i]]=;
cent[pl[i]]=;
}
tope=-;
}
};
int main()
{
//freopen("input.txt","r",stdin);
int x,y;
scanf("%d",&n);
for (int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
bfs();
init_lca();
dfs();
scanf("%d",&m);
int t;
for (int i=;i<m;i++)
{
scanf("%d",&t);
if (t==)
{
scanf("%d",&x);
printf("%d \n",n);
continue;
}
vector<int> cl;
for (int j=;j<t;j++)
{
scanf("%d\n",&ql[j].index);
ql[j].id=j;
cl.push_back(ql[j].index);
tot[ql[j].index]=;
}
sort(ql,ql+t,cmp_pos);
vector<edge> el;
tops=-;
memset(stack,,sizeof(stack));
for (int j=;j<t;j++)
{
if (tops==-)
{
stack[++tops]=ql[j].index;
}else
{
int a=lca(stack[tops],ql[j].index);
if (a==stack[tops])
{
stack[++tops]=ql[j].index;
continue;
}else
{
int a=lca(stack[tops],ql[j].index);;
while (tops && depth[a]<depth[stack[tops-]])
{
el.push_back(edge(stack[tops],stack[tops-],dis(stack[tops],stack[tops-])));
tops--;
}
el.push_back(edge(a,stack[tops],dis(a,stack[tops])));
tops--;
stack[tops+]=a;tops++;
if (stack[tops]==stack[tops-])tops--;
stack[++tops]=ql[j].index;
}
}
}
while (tops)
{
el.push_back(edge(stack[tops],stack[tops-],dis(stack[tops],stack[tops-])));
tops--;
}
//for (int j=0;j<el.size();j++)printf("edge:%d %d %d\n",el[j].x,el[j].y,el[j].v);
task2::main(el,cl);
for (int j=;j<el.size();j++)
{
assert(depth[el[j].x]>depth[el[j].y]);
int t=swim(el[j].x,depth[el[j].x]-depth[el[j].y]-);
if (el[j].gx==-)
{
tot[el[j].gy]+=siz[t]-siz[el[j].x];
}else if (el[j].gy==-)
{
tot[el[j].gx]+=siz[t]-siz[el[j].x];
}else
{
int d=swim(el[j].x,el[j].dx);
tot[el[j].gx]+=siz[d]-siz[el[j].x];
tot[el[j].gy]+=siz[t]-siz[d];
}
}
for (int j=;j<task2::pl.size();j++)
{
pair<int,int> pr=min(task2::dpson[task2::pl[j]],task2::dppnt[task2::pl[j]]);
tot[pr.second]+=task2::vsiz[task2::pl[j]];
}
sort(ql,ql+t,cmp_id);
for (int j=;j<t;j++)
printf("%d ",tot[ql[j].index]);
printf("\n");
}
}