【bzoj3611】 대공정 허수
(최근에 트리 dp의 귀속 형식을 dfs 서열에 따라 정렬한 후 거꾸로 하는 작업이 빨라지는 것을 발견했습니다!! O(NlogN)
허수 중의 모든 점에 대해sum[x]로 x를 정점으로 하는 모든 체인의 총 길이를 표시하고, f[x]는 x를 정점으로 하는 체인의 최소 값을 표시하며, g[x]는 최대 값을 표시한다.분명히 f[x]와 g[x]의 이동은 매우 편리하고 답안을 업데이트하는 것도 매우 편리하다.한편sum[x]의 이동도 매우 편리하다. 관건은 어떻게sum[x]로 답을 업데이트하는가이다.
y=fa[x](허수 중의fa를 가리키는 말), 직접 구하는 것은 매우 마법적이다. 그러나 우리는 y의 체인을 거쳐서sum[x]의 공헌을 구할 수 있다. 사실은 (sz[y]-sz[x])*sum[x]이다. 이렇게 하면 먼저 sz[]를 구할 수 있다. 실제로는 사용하지 않아도 된다. 구체적으로 아래의 코드를 볼 수 있다.
AC 코드는 다음과 같습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1000000000
#define N 1000005
#define ll long long
using namespace std;
int n,m,tot,dfsclk,fst[N],pnt[N<<1],nxt[N<<1],bin[25],pos[N],fa[N][20],d[N];
int a[N],p[N],sz[N],f[N],g[N],len[N],anc[N],q[N]; ll sum[N]; bool bo[N];
int read(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x;
}
void add(int x,int y){
pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
void dfs(int x){
pos[x]=++dfsclk; int i,p;
for (i=1; bin[i]<=d[x]; i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (p=fst[x]; p; p=nxt[p]){
int y=pnt[p];
if (y!=fa[x][0]){
fa[y][0]=x; d[y]=d[x]+1; dfs(y);
}
}
}
int lca(int x,int y){
if (d[x]<d[y]) swap(x,y); int tmp=d[x]-d[y],i;
for (i=0; bin[i]<=tmp; i++)
if (tmp&bin[i]) x=fa[x][i];
for (i=19; i>=0; i--)
if (fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; }
return (x==y)?x:fa[x][0];
}
bool cmp(int x,int y){ return pos[x]<pos[y]; }
void solve(){
m=read(); int i,tp=0,cnt=m;
for (i=1; i<=m; i++){
p[i]=a[i]=read();
bo[a[i]]=1;
}
sort(a+1,a+m+1,cmp);
for (i=1; i<=m; i++)
if (!tp){ q[++tp]=a[i]; anc[a[i]]=0; } else{
int tmp=lca(a[i],q[tp]);
for (; d[q[tp]]>d[tmp]; tp--)
if (d[q[tp-1]]<=d[tmp])
anc[q[tp]]=tmp;
if (q[tp]!=tmp){
anc[tmp]=q[tp]; q[++tp]=tmp;
p[++cnt]=tmp;
}
anc[a[i]]=tmp; q[++tp]=a[i];
}
sort(p+1,p+cnt+1,cmp);
for (i=1; i<=cnt; i++){
int x=p[i]; len[x]=d[x]-d[anc[x]];
if (bo[x]){ sz[x]=1; f[x]=g[x]=0; }
else{ sz[x]=0; f[x]=inf; g[x]=-inf; }
sum[x]=0;
}
ll t1=0; int t2=inf,t3=-inf;
for (i=cnt; i>1; i--){
int x=p[i],y=anc[x];
t1+=(sum[x]+(ll)len[x]*sz[x])*sz[y]+sum[y]*sz[x];
sz[y]+=sz[x]; sum[y]+=sum[x]+(ll)len[x]*sz[x];
t2=min(t2,f[y]+f[x]+len[x]); f[y]=min(f[y],f[x]+len[x]);
t3=max(t3,g[y]+g[x]+len[x]); g[y]=max(g[y],g[x]+len[x]);
}
for (i=1; i<=m; i++) bo[a[i]]=0;
printf("%lld %d %d
",t1,t2,t3);
}
int main(){
n=read(); int i;
bin[0]=1; for (i=1; i<=20; i++) bin[i]=bin[i-1]<<1;
for (i=1; i<n; i++){
int x=read(),y=read();
add(x,y); add(y,x);
}
dfs(1); int cas=read(); while (cas--) solve();
return 0;
}
by lych
2016.3.7
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준]3176 도로 네트워크이 문제에서는 두 도시 사이의 경로가 필요 한 것이 아니라, 두 도시 사이의 경로에서 가장 긴 도로와 가장 짧은 도로만 뭔지 알아내면 됩니다. 그렇기에 a와 (a와 b의 최소 공통 조상) 사이의 최장, 최단 도로를 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.