扬州手机网站建设,商城类网站建设报价,网站建设 艺麟盛世,六安建设机械网站点分治是世界上最好的算法QwQ 点分治可以解决各种树上的边权点权问题#xff0c;然后如果你发现这个题好像问的特别玄学#xff0c;lca#xff0c;树差都做不了#xff0c;树上动‘龟’更做不了#xff0c;只能暴力时#xff0c;这个题大多数情况就是点分治了 点分治的思… 点分治是世界上最好的算法QwQ 点分治可以解决各种树上的边权点权问题然后如果你发现这个题好像问的特别玄学lca树差都做不了树上动‘龟’更做不了只能暴力时这个题大多数情况就是点分治了 点分治的思路考虑指定p为根对于p而言树上路径分为两类过p的路径子树内的路径显然对于子树内的路径只要让他继续递归下去就行了然后我们现在要算的就是经过p的路径 算法过程 一求出来重心 二从重心开始跑dfs维护出这一段权值路径长度等 三运行calc计算对ans贡献 四从子树运行一--三 点分治时间复杂度nlogn证明被咕了 为什么非得是重心首先复杂度与最大的子树有关如果是直接往下搜y时遇到一个链会退化成$n^2 log n$若从重心开始搜保证了子树小于$\frac{n}{2}$ 运行点分治大约有两种思路第一种是暴力计算然后容斥为什么容斥被咕了第二种是类似树形背包转移再加上各种数据结构维护 两种都比较常用容斥特别好打背包适用广 我们拿几个例题看看点分治的思路 例题 聪聪可可 一颗n(n20000)个点的树上,求长度是3的倍数的路径条数。 思路清真我们统计出来各个子树内路径最后让他们合并长度余2与长度余1合并长度余3于长度余3合并最终就得到了解我们维护出每一段路径的余数 类似于 void getdeep(ll x,ll fa){tt[deep[x]%3];for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;deep[y]deep[x]edge[i];getdeep(y,x);}
}
ll calc(ll x,ll val){deep[x]val;for(ll i0;i2;i)tt[i]0;getdeep(x,0);return tt[1]*tt[2]*2tt[0]*tt[0];
} #includebits/stdc.h
using namespace std;
#define ll long long
#define Inf 1008611555ll
#define A 1000000
ll head[A],nxt[A],ver[A],edge[A],sz[A],vis[A],tt[A],deep[A];
ll size,toot,n,m,mx,ans,tot;
void add(ll x,ll y,ll z){nxt[tot]head[x],head[x]tot,ver[tot]y,edge[tot]z;
}
ll gcd(ll x,ll y){if(y0) return x;return gcd(y,x%y);
}
void gettoot(ll x,ll fa){sz[x]1;ll num0;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;gettoot(y,x);sz[x]sz[y];nummax(num,sz[y]);}nummax(num,size-sz[x]);if(nummx) mxnum,tootx;
}
void getdeep(ll x,ll fa){tt[deep[x]%3];for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;deep[y]deep[x]edge[i];getdeep(y,x);}
}
ll calc(ll x,ll val){deep[x]val;for(ll i0;i2;i)tt[i]0;getdeep(x,0);return tt[1]*tt[2]*2tt[0]*tt[0];
}
ll solve(ll x){anscalc(x,0);
// printf(x%lld t1%lld t2%lld t0%lld ans%lld\n,x,tt[1],tt[2],tt[0],ans);vis[x]1;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]) continue;ans-calc(y,edge[i]);
// printf(ans%lld\n,ans);sizesz[y];mxInf;gettoot(y,0);solve(toot);}
}
int main(){scanf(%lld,n);for(ll i1;in;i){ll x,y,z;scanf(%lld%lld%lld,x,y,z);add(x,y,z);add(y,x,z);}mxInf;sizen;gettoot(1,0);solve(toot);ll ggcd(ans,n*n);printf(%lld/%lld\n,ans/g,n*n/g);
} View Code tree 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K 思路清真我们统计出来子树之间距离然后统计一波排序一波点对一波就好了 类似于 void getdis(ll x,ll fa){q[r]d[x];for(ll ihead[x];i;inxt[i]){ll yver[i];if(yfa||vis[y]) continue;d[y]d[x]edge[i];getdis(y,x);}
}
ll calc(ll x,ll val){r0;d[x]val;getdis(x,0);ll sum0;l1;sort(q1,qr1);while(lr){if(q[l]q[r]k) sumr-l,l;else --r;}return sum;} #includebits/stdc.h
#define ll long long
#define A 1100000
#define Inf 1000000000ll
using namespace std;
ll head[A],nxt[A],ver[A],sz[A],q[A],d[A],sum[A],edge[A];
ll size,toot,mx,n,m,tot0,ans,k,l,r;
bool vis[A];
void add(ll x,ll y,ll z){ver[tot]y,nxt[tot]head[x],head[x]tot,edge[tot]z;
}
void gettoot(ll x,ll fa){sz[x]1;ll num0;for(ll ihead[x];i;inxt[i]){ll yver[i];if(yfa||vis[y]) continue;gettoot(y,x);sz[x]sz[y];nummax(num,sz[y]);}nummax(size-sz[x],num);if(nummx) mxnum,tootx;
}
void getdis(ll x,ll fa){q[r]d[x];
// printf( x%lld r%lld\n,x,r);for(ll ihead[x];i;inxt[i]){ll yver[i];if(yfa||vis[y]) continue;d[y]d[x]edge[i];getdis(y,x);}
}
ll calc(ll x,ll val){r0;d[x]val;getdis(x,0);ll sum0;l1;
// printf(r%lld l%lld\n,l,r);sort(q1,qr1);while(lr){if(q[l]q[r]k) sumr-l,l;else --r;}return sum;
}
ll solve(ll x){anscalc(x,0);vis[x]1;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]) continue;ans-calc(y,edge[i]);sizesz[y];mxInf;gettoot(y,0);solve(toot);}
}
int main(){scanf(%lld,n);for(ll i1;in;i){ll x,y,z;scanf(%lld%lld%lld,x,y,z);add(x,y,z);add(y,x,z);}scanf(%lld,k);sizen;mxInf;gettoot(1,0);solve(toot);coutansendl;
} View Code race 路径和为k且路径的边数最少 我们开一个桶维护出路径和为k时边数最小值记得清零 类似这样 void getdiss(ll x,ll fa,ll dp){if(deep[x]k)ansmin(ans,dpcnt[k-deep[x]]);for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;deep[y]deep[x]edge[i];getdiss(y,x,dp1);}
}
void uptoday(ll x,ll fa,ll dp,ll ooo){if(deep[x]k)ooo?(cnt[deep[x]]min(cnt[deep[x]],dp)):cnt[deep[x]]n;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;uptoday(y,x,dp1,ooo);}
}
void solve(ll x){vis[x]1;cnt[0]0;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]) continue;deep[y]edge[i];getdiss(y,0,1);uptoday(y,0,1,1);}for(ll ihead[x];i;inxt[i]){ll yver[i];if(!vis[y])uptoday(y,0,1,0);}for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]) continue;mxInf;sizesz[y];gettoot(y,0);solve(toot);}
} #includebits/stdc.h
using namespace std;
#define ll int
#define Inf 1e9
#define A 6100000
ll t[A10],sz[A],nxt[A],head[A],ver[A],edge[A],cnt[A],deep[A];
ll mx,size,num,k,toot,ans0,n,tot0;
bool vis[A];
void add(ll x,ll y,ll z){ver[tot]y,nxt[tot]head[x],head[x]tot,edge[tot]z;
}
void gettoot(ll x,ll fa){sz[x]1;ll num0;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;gettoot(y,x);sz[x]sz[y];nummax(num,sz[y]);}nummax(num,size-sz[x]);if(nummx) mxnum,tootx;
}
void getdiss(ll x,ll fa,ll dp){if(deep[x]k)ansmin(ans,dpcnt[k-deep[x]]);for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;deep[y]deep[x]edge[i];getdiss(y,x,dp1);}
}
void uptoday(ll x,ll fa,ll dp,ll ooo){if(deep[x]k)ooo?(cnt[deep[x]]min(cnt[deep[x]],dp)):cnt[deep[x]]n;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]||yfa) continue;uptoday(y,x,dp1,ooo);}
}
void solve(ll x){vis[x]1;cnt[0]0;for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]) continue;deep[y]edge[i];getdiss(y,0,1);uptoday(y,0,1,1);}for(ll ihead[x];i;inxt[i]){ll yver[i];if(!vis[y])uptoday(y,0,1,0);}for(ll ihead[x];i;inxt[i]){ll yver[i];if(vis[y]) continue;mxInf;sizesz[y];gettoot(y,0);solve(toot);}
}
int main(){cinnk;ansn;ll x,y,z;for(ll i1;in-1;i){cinxyz;x,y;add(x,y,z);add(y,x,z);}mxInf;sizen;for(ll i1;ik;i) cnt[i]n;gettoot(1,0);solve(toot);if(ansn)puts(-1);else printf(%d\n,ans);
} View Code 常见题目 路径和等于或小于等于k的点对路径条数。例如tree 路径和为某个数的倍数。没遇到过但也应该类似于聪聪可可 路径和为k且路径的边数最少。例如race我们只要开一个桶记录一下路径为k时最小路径 路径和mod M后为某个值。例如聪聪可可 路径上经过不允许点的个数不超过某个值且路径和最大。例如免费旅行 大多数题开一个桶i表示距离为i的相关信息有时我们也可以用一些高级数据结构例如树状数组进行一波维护。 转载于:https://www.cnblogs.com/znsbc-13/p/11249423.html
