网站开发数据库分析模板,乐清本地网站,多用户商城系统方案,潮州网站设计P3565 [POI2014]HOT-Hotels
参考题解 题目大意#xff1a; 给定一棵树#xff0c;在树上选 3 个点#xff0c;要求两两距离相等#xff0c;求方案数。 三个点树上两两距离为d存在下面两种情况
某个点三个子树#xff08;保证该点是LCA#xff09;中分别由三个点距离它为…P3565 [POI2014]HOT-Hotels
参考题解 题目大意 给定一棵树在树上选 3 个点要求两两距离相等求方案数。 三个点树上两两距离为d存在下面两种情况
某个点三个子树保证该点是LCA中分别由三个点距离它为d对于某一个点它的 d 级祖先以及子树内两个以它为LCA距它 d 的点
对于情况一设计dp fu,jf_{u,j}fu,j表示以uuu为根的子树距i距离为jjj的点数
对于情况二设计dpgu,jg_{u,j}gu,j表示以uuu为根的子树两个点的到LCA距离相等此出用d表示LCA到uuu的距离为d−jd-jd−j的点对
对于fu,jf_{u,j}fu,j的状态转移十分显然fu,j∑v∈sonufv,j−1f_{u,j}\sum_{v\in son_u }f_{v,j-1}fu,j∑v∈sonufv,j−1
而对于gu,jg_{u,j}gu,j来说存在两种情况
某个子树内部存在两个点gu,j∑v∈sonugv,j1g_{u,j}\sum_{v\in son_u}g_{v,j1}gu,j∑v∈sonugv,j1两个不同的子树各贡献一个点以uuu为LCAgu,j∑v,w∈sonu,v≠wfv,j−1×fw,j−1g_{u,j}\sum_{v,w\in son_u,v \ne w} f_{v,j-1}×f_{w,j-1}gu,j∑v,w∈sonu,vwfv,j−1×fw,j−1
很明显第二中情况fv,j−1×fw,j−1,fw,j−1×fv,j−1f_{v,j-1}×f_{w,j-1}, f_{w,j-1}×f_{v,j-1}fv,j−1×fw,j−1,fw,j−1×fv,j−1是同一种情况这里我们让vvv是uuu较靠前的儿子即可避免重复计算
而对于答案计算来说也存在两种情况 首先对于三个点树上两两距离为d的情况都可以看成两个点在一个子树中而另一个点“别处”
在子树vvv中选一个点而在其他子树中选两个点gu,j1×fv,jg_{u,j1}×f_{v,j}gu,j1×fv,j在子树vvv中选两个点而在其他子树中选一个点fu,j−1×gv,jf_{u,j-1}×g_{v,j}fu,j−1×gv,j
同样为了避免重复计算只需要让其他子树搞成vvv前面的子树即可 注意上述gu,j1g_{u,j1}gu,j1和fu,j−1f_{u,j-1}fu,j−1都还未算vvv对其的贡献这个只需要先计算答案在加贡献即可。
计算状态数组和答案时都有计算前面子树的情况直接运用前缀和的思想即可边计算答案边转移数组。
这里要提一点我们至今没有提到gu,0g_{u,0}gu,0对答案的贡献它确实对答案有贡献但是我们已经计算过了如果在此加上会重复计算。
而其他博主在计算的时候加上gu,0g_{u,0}gu,0实际上增加的时gwson,1g_{wson,1}gwson,1即重儿子的贡献。
根据g的转移方程可知道gu,0g_{u,0}gu,0的贡献全部来自于∑v∈sonugv,1\sum_{v\in son_u}g_{v,1}∑v∈sonugv,1而计算fu,j−1×gv,jf_{u,j-1}×g_{v,j}fu,j−1×gv,j对答案的贡献时我们具体写一下fu,0×gv,1f_{u,0}×g_{v,1}fu,0×gv,1而fu,01f_{u,0}1fu,01因此已经计算过gu,0g_{u,0}gu,0的贡献 然后就是长链剖分优化dp每次保存长儿子的贡献其他儿子暴力合并每条长链都会在链头暴力合并一次时间复杂度O(len)O(len)O(len)总的合并时间复杂度O(n)O(n)O(n)
最后如果写指针版本的话由于g数组是倒着转移的fff要多开一倍的内存否则g可能倒回来覆盖掉fff
code
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr int N5010;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;}
int n;
int dep[N],son[N];
void dfs1(int u,int fa)
{for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;dfs1(v,u);if(dep[v]dep[son[u]]) son[u]v;}dep[u]dep[son[u]]1;
}ll pool[4*N];
ll *f[N],*g[N],*nowpool;
ll ans;
void dfs2(int u,int fa)
{f[u][0]1;if(son[u]){f[son[u]]f[u]1;g[son[u]]g[u]-1;dfs2(son[u],u);ansg[son[u]][1];// 加上重儿子的贡献}for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa||vson[u]) continue;f[v]now;nowdep[v]1;g[v]now;nowdep[v];dfs2(v,u);// 边计算for(int j0;jdep[v];j){if(j) ansf[u][j-1]*g[v][j];ansg[u][j1]*f[v][j];}// 边转移for(int j0;jdep[v];j){g[u][j1]f[u][j1]*f[v][j];if(j) g[u][j-1]g[v][j];f[u][j1]f[v][j];}}}
int main()
{IO;cinn;memset(h,-1,sizeof h);for(int i1;in;i){int u,v;cinuv;add(u,v);add(v,u);}dfs1(1,0);f[1]now;nowdep[1]1;//多开一倍的内存g[1]now;nowdep[1];dfs2(1,0);coutans\n;return 0;
}菜菜的我搞了一天这个题啊啊啊啊
