做网站必须要认证吗,网站的购物车怎么做,软装设计的意义,国家世界新闻洛谷P3233 [HNOI2014]世界树
题目大意
有一棵 n n n个点的树#xff0c;每个点有一个编号#xff0c;有 q q q次操作。对于每次操作#xff0c;给出 m m m个点并称为议事点#xff0c;树上各个点由离这个点最近的议事点管理#xff08;如果有多个议事点离这个点最近每个点有一个编号有 q q q次操作。对于每次操作给出 m m m个点并称为议事点树上各个点由离这个点最近的议事点管理如果有多个议事点离这个点最近则这个点由这些议事点中编号最小的点管理。求每次操作中每个议事点管理的点的数目。 1 ≤ n ≤ 3 × 1 0 5 , 1 ≤ q ≤ 3 × 1 0 5 , 1 ≤ ∑ m i ≤ 3 × 1 0 5 1\leq n\leq 3\times 10^5,1\leq q\leq 3\times 10^5,1\leq \sum m_i\leq 3\times 10^5 1≤n≤3×105,1≤q≤3×105,1≤∑mi≤3×105 题解
前置知识虚树
如果直接 d f s dfs dfs的话则要通过两遍 d f s dfs dfs。对于一个非议事点 u u u先用 u u u的子树中离 u u u最近的议事点来更新 u u u再用 u u u的子树之外的离 u u u最近的议事点来更新 u u u。
下面是暴力的代码。
code
void dfs1(int u,int fa){dis[u]inf;for(int ir[u];i;il[i]){if(d[i]fa) continue;dfs(d[i],u);if(dis[d[i]]1dis[u]){dis[u]dis[d[i]]1;to[u]to[d[i]];}else if(dis[d[i]]1dis[u]){to[u]min(to[u],to[d[i]]);}}if(z[u]){dis[u]0;to[u]u;}
}
void dfs2(int u,int fa){for(int ir[u];i;il[i]){if(d[i]fa) continue;if(dis[u]1dis[d[i]]){dis[d[i]]dis[u]1;to[d[i]]to[u];}else if(dis[u]1dis[d[i]]){to[d[i]]min(to[d[i]],to[u]);}dfs2(d[i],u);}z[u]0;
}因为 1 ≤ ∑ m i ≤ 3 × 1 0 5 1\leq \sum m_i\leq 3\times 10^5 1≤∑mi≤3×105所以我们可以用虚树来解决问题。
对于每次操作建一棵虚树。对于虚树上的点用上面的 d f s dfs dfs跑一Bianc遍即可。
那不在虚树上的点怎么判断呢
我们要分两种情况
如果原树上有一个点 u u u它有一个儿子 v v v且 v v v的子树中没有议事点则子树 v v v中的每个点肯定都是由离 u u u最近的议事点管理如果虚树上有一个点 u u u它有一个儿子 v v v且 u u u和 v v v之间含有若干个点则用倍增求 u u u和 v v v之间的这条链上的分界点分界点及以下的部分由离 v v v最近的议事点管理分界点以上的部分由离 u u u最近的议事点管理注意链上附带的点也根据在分界点的上面或下面来判断由哪个议事点管理
对于第一种情况在 d f s dfs dfs时对每个议事点的答案加上其子树的大小即可。
对于第二种情况将分界点 x x x及以下的点的数量即 s i z [ x ] − s i z [ v ] siz[x]-siz[v] siz[x]−siz[v]加在离 v v v最近的议事点上将分界点以上的点的数量因为在第一种情况中已经加上了每个议事点的子树大小所以只需要减去 s i z [ x ] siz[x] siz[x]加在离 u u u最近的议事点上。
时间复杂度为 O ( n log n ∑ m log m ) O(n\log n\sum m\log m) O(nlogn∑mlogm)。
code
#includebits/stdc.h
using namespace std;
const int N300005,inf1e9;
int n,q,k,tot0,wt0,top0,d[N*2],l[N*2],r[N*2],a[N],b[N];
int dep[N],dfn[N],siz[N],s[N],z[N],dis[N],to[N],ans[N],f[N][20];
vectorintv[N];
int cmp(int ax,int bx){return dfn[ax]dfn[bx];
}
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void pt(int u,int fa){dfn[u]wt;dep[u]dep[fa]1;siz[u]1;f[u][0]fa;for(int i1;i19;i){f[u][i]f[f[u][i-1]][i-1];}for(int ir[u];i;il[i]){if(d[i]fa) continue;pt(d[i],u);siz[u]siz[d[i]];}
}
int gt(int x,int y){if(dep[x]dep[y]) swap(x,y);for(int i19;i0;i--){if(dep[f[x][i]]dep[y]) xf[x][i];}if(xy) return x;for(int i19;i0;i--){if(f[x][i]!f[y][i]){xf[x][i];yf[y][i];}}return f[x][0];
}
void insert(int x){if(top1){s[top]x;return;}int lcagt(x,s[top]);while(top1dfn[s[top-1]]dfn[lca]){v[s[top-1]].push_back(s[top]);--top;}if(s[top]!lca){v[lca].push_back(s[top]);s[top]lca;}s[top]x;
}
void dd(int x,int y){int uy;for(int i19;i0;i--){int v1,v2;v1dep[y]-dep[f[u][i]]dis[y];v2dep[f[u][i]]-dep[x]dis[x];if(dep[f[u][i]]dep[x](v1v2||v1v2to[y]to[x])) uf[u][i];}ans[to[y]]siz[u]-siz[y];ans[to[x]]-siz[u];
}
void dfs1(int u,int fa){dis[u]inf;for(int i0;iv[u].size();i){int ev[u][i];dfs1(e,u);int vtdep[e]-dep[u];if(dis[e]vtdis[u]){dis[u]dis[e]vt;to[u]to[e];}else if(dis[e]vtdis[u]){to[u]min(to[u],to[e]);}}if(z[u]){dis[u]0;to[u]u;}
}
void dfs2(int u,int fa){for(int i0;iv[u].size();i){int ev[u][i];int vtdep[e]-dep[u];if(dis[u]vtdis[e]){dis[e]dis[u]vt;to[e]to[u];}else if(dis[u]vtdis[e]){to[e]min(to[e],to[u]);}dd(u,e);dfs2(e,u);}ans[to[u]]siz[u];z[u]0;v[u].clear();
}
int main()
{scanf(%d,n);for(int i1,x,y;in;i){scanf(%d%d,x,y);add(x,y);add(y,x);}pt(1,0);scanf(%d,q);while(q--){scanf(%d,k);for(int i1;ik;i){scanf(%d,a[i]);b[i]a[i];z[a[i]]1;ans[a[i]]0;}sort(a1,ak1,cmp);s[top1]1;for(int i1;ik;i){if(a[i]!1) insert(a[i]);}while(top1){v[s[top-1]].push_back(s[top]);--top;}dfs1(1,0);dfs2(1,0);for(int i1;ik;i){printf(%d ,ans[b[i]]);}printf(\n);}return 0;
}
