博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
P2634 [国家集训队]聪聪可可
阅读量:5291 次
发布时间:2019-06-14

本文共 3085 字,大约阅读时间需要 10 分钟。

点分治入门题

首先可以直接枚举所有两点的lca强行dp

设 $f [ x ] [ 0/1/2 ]$ 表示节点 $x$ 在模3意义下,$x$ 的子树所有节点到 $x$ 的距离为 $0/1/2$ 时的方案数

初始 $f [ x ] [ 0 ] =1$ (本身到自己有一种方案)

转移就枚举所有儿子 $v$ ,设 $x$ 到 $v$ 的距离为 $w$,那么转移显然为:

$ f [ x ] [ (w+0)\%3 ] += f [ v ] [ 0 ] $ 

$ f [ x ] [ (w+1)\%3 ] += f [ v ] [ 1 ] $ 

$ f [ x ] [ (w+2)\%3 ] += f [ v ] [ 2 ] $ 

统计答案也十分显然,对 $w$ 分类讨论一下就好了:

inline void work(int x)//注意函数名不是"dfs",x就是我们枚举的lca{    f[x][0]=1; f[x][1]=f[x][2]=0;    for(int i=fir[x];i;i=from[i])    {        int &v=to[i],&w=val[i]; if(vis[v]) continue; dfs(v,x);//dfs求出儿子的f        if(w==0) ans+=f[x][0]*f[v][0]+f[x][1]*f[v][2]+f[x][2]*f[v][1];        if(w==1) ans+=f[x][0]*f[v][2]+f[x][1]*f[v][1]+f[x][2]*f[v][0];        if(w==2) ans+=f[x][0]*f[v][1]+f[x][1]*f[v][0]+f[x][2]*f[v][2];      //注意先统计ans再转移f        f[x][w]+=f[v][0];        f[x][fk(w+1)]+=f[v][1];        f[x][fk(w+2)]+=f[v][2];    }}

但是最坏情况会被卡到 $O(n^2)$

所以上点分治,每次找重心作lca,这样每次子树大小至少减半

枚举lca复杂度$O(n)$,搞dp因为子树大小每次减半所以复杂度约为 $O(log_n)$

总复杂度 $O(nlog_n)$

注意long long

#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=5e5+7,INF=1e9+7;int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt;inline void add(int &a,int &b,int &c){ from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c;}inline int fk(int x) { return x>=3 ? x-3 : x; }int n,rt,tot;ll ans,f[N][3];int sz[N],mx[N];bool vis[N];void find_rt(int x,int fa)//找重心{ mx[x]=0; sz[x]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(vis[v]||v==fa) continue; find_rt(v,x); sz[x]+=sz[v]; mx[x]=max(mx[x],sz[v]); } mx[x]=max(mx[x],tot-sz[x]); if(mx[x]
点分治解法

其实此题不用点分治

可以直接树形dp,转移同上...代码又短又好写

#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=5e5+7;inline int fk(int x) { return x>=3 ? x-3 : x; }int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt;inline void add(int &a,int &b,int &c){ from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c;}ll ans,f[N][3];void dfs(int x,int fa){ f[x][0]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i],&w=val[i]; if(v==fa) continue; dfs(v,x); if(w==0) ans+=f[x][0]*f[v][0]+f[x][1]*f[v][2]+f[x][2]*f[v][1]; if(w==1) ans+=f[x][0]*f[v][2]+f[x][1]*f[v][1]+f[x][2]*f[v][0]; if(w==2) ans+=f[x][0]*f[v][1]+f[x][1]*f[v][0]+f[x][2]*f[v][2]; f[x][w]+=f[v][0]; f[x][fk(w+1)]+=f[v][1]; f[x][fk(w+2)]+=f[v][2]; }}int n;ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; }int main(){ int a,b,c; n=read(); for(int i=1;i

 

转载于:https://www.cnblogs.com/LLTYYC/p/10302855.html

你可能感兴趣的文章
利用 Gearman 实现系统错误报警功能
查看>>
HDU 4035 期望dp
查看>>
bzoj 2301 莫比乌斯反演
查看>>
Tensor索引操作
查看>>
mongoose连表查询2
查看>>
html5 SVG
查看>>
.Net学习 第2季06 C#面向对象 Path类 File类 FileStream类 StreamReader/StreamWriter类
查看>>
VS2008+Qt 项目目录编辑配置
查看>>
【动态规划DP】传娃娃-C++
查看>>
LOJ.121.[离线可过]动态图连通性(线段树分治 按秩合并)
查看>>
201521123072 结对编程
查看>>
最长上升子序列
查看>>
maven 依赖、聚合和继承 (转)
查看>>
selinux介绍/状态查看/开启/关闭
查看>>
DockerAPI版本不匹配的问题
查看>>
Leetcode: Ugly Number II
查看>>
项目立项管理
查看>>
(没时间维护,已下架)博客园第三方客户端-i博客园正式发布App Store
查看>>
map使用实例
查看>>
关于ShapeDrawable应用的一些介绍(上)
查看>>