POI2014 Hot-Hotels 题解
$\text{Description}$
给定一棵树,求树上存在多少个三元组 $(a,b,c)$,满足 $\operatorname{dis}(a,b)=\operatorname{dis}(a,c)=\operatorname{dis}(b,v)$。
$n\le 10^5$
$\text{Solution}$
为了将来优化复杂度,我们先以 $1$ 为根。考虑满足条件的三元组会呈现什么样的形态:
对于第一种情况,我们容易想到令 $f_{i,j}$ 表示 $i$ 的子树中到 $i$ 距离为 $j$ 的节点个数。但是直接对每个节点的每个深度进行统计会重复,我们先来考虑第二种情况。考虑令 $g_{i,j}$ 表示 $i$ 的子树中,有多少二元组 $(a,b)$ 满足 $\operatorname{dis}(\operatorname{LCA}(a,b),a)=\operatorname{dis}(\operatorname{LCA(a,b),b})=\operatorname{dis}(\operatorname{LCA}(a,b),i)+j$。那么第一种情况可以看成:
这样的话,只需保证左边的节点和右边两个节点不在某一个点的同一个儿子的子树内,那么就不会被重复统计。
那么,节点 $now$ 对答案的贡献应是:
上式的主要问题在于,我们要让左节点和右二节点不在同一个儿子的子树内,所以需要枚举不同的儿子进行统计,那么深度那一维也需要发生相应的改变。
$f$ 的转移比较容易:
接下来考虑 $g$ 的转移。我们发现,$g$ 可以有两种从儿子转移的方式:
对于第一种情况,其实就是 $j$ 少了一个。对于第二种情况,发现 $\operatorname{LCA}(a,b)=now$,那么 $\operatorname{dis}(\operatorname{LCA}(a,b),a)=\operatorname{dis}(\operatorname{LCA}(a,b),b)=j$,然后 $now$ 到它本身的距离显然为 $0$,故就差了 $j$,于是有:
这样的话,我们得到了一个 $O(n^2)$ 的动态规划方程,但是要想达到这个复杂度需要用到前缀和,具体参考代码。
然后发现以深度为下标的话,可以使用长链剖分优化至 $O(n)$。具体请参考代码及代码注释。
$\text{Code}$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include<bits/stdc++.h> #define REG register #define MAXN 100005 #define LL long long #define FORE(i,now) for(REG int i=head[now];i;i=ed[i].nxt) using namespace std; inline int read(){ REG int x(0); REG char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x*10)+(c^48),c=getchar(); return x; }
struct Edge{ int v,nxt; }ed[MAXN<<1]; int head[MAXN],cnt; inline void adde(int u,int v){ed[++cnt]=(Edge){v,head[u]},head[u]=cnt;} inline void add(int u,int v){adde(u,v),adde(v,u);}
int n;
LL *f[MAXN],*g[MAXN],*p,G[MAXN<<2],ans; int Son[MAXN],Len[MAXN];
void dfs1(int now,int fa){ FORE(i,now){ int v=ed[i].v; if(v==fa) continue; dfs1(v,now); if(Len[v]>Len[Son[now]]) Son[now]=v; } Len[now]=Len[Son[now]]+1; }
inline void Assign(int now){f[now]=p,p+=Len[now]<<1,g[now]=p,p+=Len[now]<<1;}
void dfs2(int now,int fa){ if(Son[now]) f[Son[now]]=f[now]+1,g[Son[now]]=g[now]-1,dfs2(Son[now],now); f[now][0]=1,ans+=g[now][0]; FORE(i,now){ int v=ed[i].v; if(v==fa||v==Son[now]) continue; Assign(v),dfs2(v,now); for(REG int j=0;j<Len[v];++j){ if(j) ans+=f[now][j-1]*g[v][j]; ans+=g[now][j+1]*f[v][j]; } for(REG int j=0;j<Len[v];++j){ g[now][j+1]+=f[now][j+1]*f[v][j]; if(j) g[now][j-1]+=g[v][j]; f[now][j+1]+=f[v][j]; } } }
void Work(){ n=read(); for(REG int i=1;i<n;++i) add(read(),read()); dfs1(1,0); p=G,Assign(1); dfs2(1,0); printf("%lld\n",ans); }
int main(){ Work(); }
|