洛谷P3233 [HNOI2014]世界树

虚树= =

 #include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define INF 0x7f7f7f7f
#define MAXN 300005
#define LOG 20
#define rint register int
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define ft first
#define sc second
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int fst1[MAXN],nxt1[MAXN<<],from1[MAXN<<],to1[MAXN<<],cnte;
int fst[MAXN],nxt[MAXN<<],from[MAXN<<],to[MAXN<<],cnt;
void add(int x,int y){
nxt[++cnt]=fst[x],fst[x]=cnt,from[cnt]=x,to[cnt]=y;
nxt[++cnt]=fst[y],fst[y]=cnt,from[cnt]=y,to[cnt]=x;
}
void add1(int x,int y){
nxt1[++cnte]=fst1[x],fst1[x]=cnte,from1[cnte]=x,to1[cnte]=y;
nxt1[++cnte]=fst1[y],fst1[y]=cnte,from1[cnte]=y,to1[cnte]=x;
}
int n,m;
int h[MAXN];
int dep[MAXN],fa[MAXN][LOG],sz[MAXN];
int dfn[MAXN],idx;
int b[MAXN],pa[MAXN];
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(rint d=dep[x]-dep[y],k=;d;d>>=,k++){
if(d&)x=fa[x][k];
}
if(x==y)return x;
for(rint k=LOG-;k>=;k--){
if(fa[x][k]!=fa[y][k]){
x=fa[x][k],y=fa[y][k];
}
}
return fa[x][];
}
void dfs1(int x){
sz[x]=;
dfn[x]=(++idx);
for(rint e=fst1[x];e;e=nxt1[e]){
int y=to1[e];
if(y!=fa[x][]){
fa[y][]=x;
dep[y]=dep[x]+;
dfs1(y);
sz[x]+=sz[y];
}
}
}
bool comp(const int &A,const int &B){
return (dfn[A]<dfn[B]);
}
bool comp1(const int A,const int &B){
return (dep[A]>dep[B]);
}
int sta[MAXN],top,rt,t[MAXN],tot;
pii d[MAXN];
void dfs(int x){
for(rint e=fst[x];e;e=nxt[e]){
int y=to[e];
if(y!=pa[x]){
d[y]=min(d[y],mp(d[x].ft+dep[y]-dep[x],d[x].sc));
dfs(y);
}
}
}
void pop(int p){
pa[sta[top]]=p;
add(sta[top],p);
b[sta[top]]=;
t[++tot]=sta[top];
top--;
}
int h1[MAXN];
void init(){
cnt=;
memset(fst,,sizeof(fst));
memset(nxt,,sizeof(nxt));
memset(from,,sizeof(from));
memset(to,,sizeof(to));
memset(b,,sizeof(b));
memset(pa,,sizeof(pa));
memcpy(h1,h,sizeof(h1));
sort(h+,h+m+,comp);
top=tot=;
sta[++top]=h[];
int x,y;
for(rint i=;i<=m;i++){
x=h[i],y=lca(x,sta[top]);
while(dep[sta[top-]]>=dep[y]){
pop(sta[top-]);
}
if(dep[sta[top]]==dep[y]){
sta[++top]=x;
}
else{
pop(y);
sta[++top]=y;
sta[++top]=x;
}
}
while(top){
pop(sta[top-]);
}
rt=sta[];
for(rint i=;i<=tot;i++)d[t[i]]=mp(INF,);
for(rint i=;i<=m;i++)d[h[i]]=mp(,h[i]);
sort(t+,t+tot+,comp1);
for(rint i=;i<=tot;i++){
x=t[i];
d[pa[x]]=min(d[pa[x]],mp(d[x].ft-dep[pa[x]]+dep[x],d[x].sc));
}
dfs(rt);
}
int ans[MAXN];
int LA(int x,int L){
for(rint k=L,p=;k;k>>=,p++){
if(k&){
x=fa[x][p];
}
}
return x;
}
int workup(int x,int f,int L){
if(L<=)return ;
int y=LA(x,min(L,dep[x]-dep[f]-));
return sz[y]-sz[x];
}
int workdown(int x,int f,int L){
if(L<=)return ;
int y=LA(x,dep[x]-dep[f]-);
int z=LA(x,max(dep[x]-dep[f]--L,));
return sz[y]-sz[z];
}
void work(int x,int f){
int t=d[f].ft+d[x].ft+dep[x]-dep[f]-;
int L=t>>;
if(t&){
ans[d[x].sc]+=workup(x,f,L-d[x].ft);
ans[d[f].sc]+=workdown(x,f,L-d[f].ft);
ans[min(d[x].sc,d[f].sc)]+=workup(x,f,L+-d[x].ft)-workup(x,f,L-d[x].ft);
}
else{
ans[d[x].sc]+=workup(x,f,L-d[x].ft);
ans[d[f].sc]+=workdown(x,f,L-d[f].ft);
}
}
void solve(){
memset(ans,,sizeof(ans));
int x;
for(rint i=;i<=tot;i++){
x=t[i];
ans[d[x].sc]+=sz[x];
int y=LA(x,dep[x]-dep[pa[x]]-);
ans[d[pa[x]].sc]-=sz[y];
}
ans[d[rt].sc]+=sz[]-sz[rt];
for(rint i=;i<=tot;i++){
x=t[i];if(x==rt)continue;
work(x,pa[x]);
}
for(rint i=;i<=m;i++){
printf("%d ",ans[h1[i]]);
}printf("\n");
}
int main()
{
// freopen("data.in","r",stdin);
n=read();
int x,y;
for(rint i=;i<n;i++){
x=read(),y=read();
add1(x,y);
}
dep[]=;
dfs1();
for(rint k=;k<LOG;k++){
for(rint i=;i<=n;i++){
fa[i][k]=fa[fa[i][k-]][k-];
}
}
int q=read();
while(q--){
m=read();
for(rint i=;i<=m;i++)h[i]=read();
init();
solve();
}
return ;
}
上一篇:leetcode@ [174] Dungeon Game (Dynamic Programming)


下一篇:hdu5046(重复覆盖+二分)