建站行业最新消息,大数据营销平台那么多,实现微信绑定登录网站,新闻播报最新点分治就是树上的分治#xff0c;也就是处理把分治强行搬到树上的毒瘤问题。
算法流程
引入#xff1a;[国家集训队]聪聪可可 #xff08;各大OJ搜索即可#xff09;
题意#xff1a;给一棵树#xff0c;随机选两个点#xff08;可以相同#xff09;#xff0c;求距…点分治就是树上的分治也就是处理把分治强行搬到树上的毒瘤问题。
算法流程
引入[国家集训队]聪聪可可 各大OJ搜索即可
题意给一棵树随机选两个点可以相同求距离为3的倍数的概率。
显然求长度是3的倍数的路径数即可。
首先是分治那我们考虑一个子问题即一棵树。
然而树上没有中点。如果直接分给条链就挂了。
所以我们yy一个中点重心
重心定义是以它为根的子树size的最大值最小。
因为是树所以至少有两个子树。又是均分的可以保证log
我们先找出重心然后乱搞求过重心的路径数。
然后递归就可以解决。
实现
口胡和实现难度差别最大的算法。
首先需要一个findroot来找重心。
开一个cut数组记录被砍掉的节点相当于移出游戏 。
用solve控制流程。进入solve后马上砍掉root
然后马上用calc计算当前子问题。
calc中用dfs处理子树信息并顺便求出大小然后整合答案并更新。注意清零。
此过程中一定不要吝啬空间可以重新开个数组记录修改的地方算完后再依次还原。最好开临时数组记录当前子树并和之前统计答案算完后合并。千万不要memset用for也要仔细算复杂度。
当然本题很友好只有三个变量。
回到solve用dfs中求出的大小找子树中的重心并递归。
代码
风格可能和大众不同仅供参考
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 20005
#define MAXM 40005
#define INF 0x7fffffff
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int n;
struct edge
{int u,v,w;
}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
bool cut[MAXN];
int ans;
int root,siz[MAXN],maxp[MAXN];
void findroot(int u,int f,int sum)
{siz[u]1,maxp[u]0;for (int ihead[u];i;inxt[i])if (e[i].v!f!cut[e[i].v]){findroot(e[i].v,u,sum);siz[u]siz[e[i].v];maxp[u]max(maxp[u],siz[e[i].v]);}if (sum-siz[u]maxp[u]) maxp[u]sum-siz[u];if (maxp[u]maxp[root]) rootu;
}
int tot[3],tt[3];
int dfs(int u,int f,int s)
{int ans1;tt[s];for (int ihead[u];i;inxt[i])if (e[i].v!f!cut[e[i].v])ansdfs(e[i].v,u,(se[i].w)%3);return ans;
}
int sum[MAXN];
void calc()
{tot[0]1,tot[1]tot[2]0;for (int ihead[root];i;inxt[i])if (!cut[e[i].v]){tt[0]tt[1]tt[2]0;sum[e[i].v]dfs(e[i].v,0,e[i].w);anstot[0]*tt[0]tot[1]*tt[2]tot[2]*tt[1];tot[0]tt[0],tot[1]tt[1],tot[2]tt[2];}
}
void solve()
{cut[root]1;calc();for (int ihead[root];i;inxt[i])if (!cut[e[i].v]){maxp[root0]INF;findroot(e[i].v,0,sum[e[i].v]);solve();}
}
int gcd(const int a,const int b){return b? gcd(b,a%b):a;}
void print(int a,int b)
{int ggcd(a,b);a/g,b/g;printf(%d/%d,a,b);
}
int main()
{nread();for (int i1;in;i){int u,v,w;uread(),vread(),wread()%3;addnode(u,v,w),addnode(v,u,w);}maxp[0]INF;findroot(1,0,n);solve();print(2*ansn,n*n);return 0;
}[IOI2011]Race
题意给定一棵树和k求长为k的路径中最小的边数。k≤1000000k \leq 1000000k≤1000000
其它一样主要是calc
开个1e6的数组dis记录长为i的路径最小边数
用tdis记录当前子树dfs时更新
用q和tq记录dis和tdis修改的下标算完后还原成INF
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 200005
#define MAXM 400005
#define MAXV 1000005
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) {if (c-) f-1;cgetchar();}while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
int n,k;
struct edge{int u,v,w;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
bool cut[MAXN];
int root;
int siz[MAXN],maxp[MAXN];
void findroot(int u,int f,int s)
{siz[u]1,maxp[u]0;for (int ihead[u];i;inxt[i])if (!cut[e[i].v]e[i].v!f){findroot(e[i].v,u,s);siz[u]siz[e[i].v];maxp[u]max(maxp[u],siz[e[i].v]);}if (s-siz[u]maxp[u]) maxp[u]s-siz[u];if (maxp[u]maxp[root]) rootu;
}
int dis[MAXV],tdis[MAXV],sum[MAXN];
int q[MAXN],top,tq[MAXN],tt;
int dfs(int u,int f,int s,int d)
{int ans1;if (sk) tdis[tq[tt]s]min(tdis[s],d);for (int ihead[u];i;inxt[i])if (!cut[e[i].v]e[i].v!f)ansdfs(e[i].v,u,se[i].w,d1);return ans;
}
int ansINF;
void calc()
{dis[0]top0;for (int ihead[root];i;inxt[i])if (!cut[e[i].v]){tt0;sum[e[i].v]dfs(e[i].v,0,e[i].w,1);for (int i1;itt;i) ansmin(ans,tdis[tq[i]]dis[k-tq[i]]);for (int i1;itt;i) dis[tq[i]]min(dis[tq[i]],tdis[tq[i]]),q[top]tq[i];for (int i1;itt;i) tdis[tq[i]]INF; }for (int i1;itop;i) dis[q[i]]INF;
}
void solve()
{cut[root]true;calc();for (int ihead[root];i;inxt[i])if (!cut[e[i].v]){maxp[root0]INF;findroot(e[i].v,0,sum[e[i].v]);solve();}
}
int main()
{nread(),kread();for (int i1;in;i){int u,v,w;uread()1,vread()1,wread();addnode(u,v,w),addnode(v,u,w);}maxp[root0]INF;findroot(1,0,n);memset(dis,0x3f,sizeof(dis)sizeof(tdis));solve();printf(%d\n,(ansINF? -1:ans));return 0;
}
