bzoj4543: [POI2014] 호텔 강화판(긴 체인 해부+dp)

전송문 코드: 긴 사슬로 문제를 나누세요.제목: 나무 한 그루를 주고 나무에 서로 다른 세 개의 노드를 골라서 이 세 개의 점과 두 개의 거리를 똑같이 하는 방안을 물어보세요.
사고: 먼저 dpdpdp를 고려한다.f i , j f_{i, j}fi, j는 i i i 서브트리에서 i i i 거리가 j j의 포인트임을 나타낸다. g i, j g{i, j} gi, j는 i i i 서브트리에 있는 모든 만족 di st(l c a(u, v), i) - d i st(l c a(u, v), i) = j dist(lca(u, v), i)-dist(lca(u, v), i) = j dist(lca(u, v), i) = j dist(u, v) - dist(lca, u, v), i) = j의 점 대수를 나타냅니다.이 두 상태가 조립할 수 있다는 것을 발견하기 어렵지 않다.따라서 한 쌍의 아버지와 아이(p, v)(p, v)(p, v)에 대해 다음과 같은 이동식이 있다. a n s + = g v, i + 1 ∗ f p, i + g p, i ∗ f v, i - 1 ans + = g{v,i+1}*f_{p,i}+g_{p,i}*f_{v,i-1} ans+=gv,i+1​∗fp,i​+gp,i​∗fv,i−1​ g p , i + = g v , i − 1 + f v , i − 1 ∗ f p , i g_{p,i}+=g_{v,i-1}+f_{v,i-1}*f_{p,i} gp,i​+=gv,i−1​+fv,i−1​∗fp,i​ f p , i + = f v , i − 1 f_{p,i}+=f_{v, i-1} fp, i+=fv, i-3-1 그리고 긴 체인으로 나누어 최적화하면 됩니다.코드:

#include
#define ri register int
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
typedef long long ll;
const int N=1e5+5;
vector<int>e[N];
int n,hson[N],dep[N],mdep[N],len[N],fa[N];
ll tmp[N<<2],*f[N],*g[N],*now=tmp,ans=0;
void dfs1(int p){
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fa[p])continue;
		fa[v]=p,dep[v]=mdep[v]=dep[p]+1,dfs1(v),mdep[p]=max(mdep[p],mdep[v]);
		if(mdep[v]>mdep[hson[p]])hson[p]=v;
	}
	len[p]=mdep[p]-dep[p]+1;
}
void dfs2(int p){
	if(hson[p])f[hson[p]]=f[p]+1,g[hson[p]]=g[p]-1,dfs2(hson[p]);
	f[p][0]=1,ans+=g[p][0];
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fa[p]||v==hson[p])continue;
		f[v]=now,now+=2*len[v],g[v]=now,now+=2*len[v],dfs2(v);
		for(ri j=0;j<len[v];++j){
			ans+=f[v][j]*g[p][j+1];
			if(j)ans+=g[v][j]*f[p][j-1];
		}
		for(ri j=0;j<len[v];++j){
			g[p][j+1]+=f[v][j]*f[p][j+1];
			if(j)g[p][j-1]+=g[v][j];
			f[p][j+1]+=f[v][j];
		}
	}
}
int main(){
	freopen("lx.in","r",stdin);
	while(n=read(),n){
		ans=0;
		memset(tmp,0,sizeof(tmp));
		memset(hson,0,sizeof(hson));
		memset(mdep,0,sizeof(mdep));
		for(ri i=1;i<=n;++i)e[i].clear();
		for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
		dfs1(1),now=tmp,f[1]=now,now+=2*len[1],g[1]=now,now+=2*len[1],dfs2(1),cout<<ans<<'
';
	}
	return 0;
}