- 1.Tree
- Description:
求一棵树中长度不超过 \(K\) 的路径条数
Solution:
直接统计深度, 由于深度的贡献具有单调性
考虑每次统计答案时先排序, 然后双指针每次相减
这样就比 \(n^2\) 统计优秀多了, 记得要减掉算重的
2.[模版] 点分治 1
Description:
求一棵树中是否存在长度为 \(K\) 的链,\(m\) 组询问,\(m \le 100\)
Solution:
考虑每次用桶把路径长度标记, 把所有询问在桶里查一遍, 再清空桶
复杂度 \(O(nmlog^2n)\)
- #include <map>
- #include <set>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <iostream>
- #include <algorithm>
- #define ls p<<1
- #define rs p<<1|1
- using namespace std;
- typedef long long ll;
- const int mxn=1e5+5,inf=1e7;
- int n,m,s,rt,cnt,tot,sumsz,f[mxn],hd[mxn],sz[mxn],vis[mxn],dis[mxn],ask[mxn],ans[mxn],tag[mxn],dep[mxn],bac[inf+5];
- inline int read() {
- char c=getchar(); int x=0,f=1;
- while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
- while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
- return x*f;
- }
- inline void chkmax(int &x,int y) {if(x<y) x=y;}
- inline void chkmin(int &x,int y) {if(x>y) x=y;}
- struct ed {
- int to,nxt,w;
- }t[mxn<<1];
- inline void add(int u,int v,int w) {
- t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
- }
- int getrt(int u,int fa) {
- sz[u]=1; f[u]=0;
- for(int i=hd[u];i;i=t[i].nxt) {
- int v=t[i].to;
- if(v==fa||vis[v]) continue ;
- getrt(v,u); sz[u]+=sz[v];
- chkmax(f[u],sz[v]);
- }
- chkmax(f[u],sumsz-sz[u]);
- if(f[u]<f[rt]) rt=u;
- }
- void getdis(int u,int fa) {
- dis[++tot]=dep[u];
- for(int i=hd[u];i;i=t[i].nxt) {
- int v=t[i].to;
- if(v==fa||vis[v]) continue ;
- dep[v]=dep[u]+t[i].w; getdis(v,u);
- }
- }
- void cal(int u) {
- s=0;
- for(int i=hd[u];i;i=t[i].nxt) {
- int v=t[i].to;
- if(vis[v]) continue ;
- dep[v]=t[i].w; tot=0; getdis(v,u);
- for(int j=1;j<=m;++j) {
- for(int k=1;k<=tot;++k) {
- if(dis[k]>ask[j]) break ;
- ans[j]|=bac[ask[j]-dis[k]];
- }
- }
- for(int k=1;k<=tot;++k)
- if(dis[k]<=inf) bac[dis[k]]=1,tag[++s]=dis[k];
- }
- for(int i=1;i<=s;++i) bac[tag[i]]=0; bac[0]=1;
- }
- void solve(int u) {
- vis[u]=1; cal(u);
- for(int i=hd[u];i;i=t[i].nxt) {
- int v=t[i].to;
- if(vis[v]) continue ;
- sumsz=sz[v]; rt=0;
- getrt(v,u); solve(rt);
- }
- }
- int main()
- {
- n=read(); m=read(); int u,v,w; bac[0]=1;
- for(int i=1;i<n;++i) {
- u=read(); v=read(); w=read();
- add(u,v,w); add(v,u,w);
- }
- for(int i=1;i<=m;++i) ask[i]=read();
- rt=0; sumsz=f[0]=n; getrt(1,0); solve(rt);
- for(int i=1;i<=m;++i)
- if(ans[i]) puts("AYE"); else puts("NAY");
- return 0;
- }
3. 聪聪可可
Description:
给你一棵树, 询问有多少条路径满足边权和为 3 的倍数
Solution:
和 Tree 差不多...... 统计时开 3 个桶, 乘法原理搞一下就行
- 4.Distance in Tree
- Description:
给你一棵树, 问路径长为 K 的条数
Solution:
方法同 2, 如果你无聊的话可以写个类似 Tree 的写法用 <=k 的减去 < k 的
- #include <map>
- #include <set>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <iostream>
- #include <algorithm>
- #define ls p<<1
- #define rs p<<1|1
- using namespace std;
- typedef long long ll;
- const int mxn=1e5+5;
- int n,m,k,rt,cnt,tot,ans,sumsz,f[mxn],hd[mxn],sz[mxn],bac[mxn],dep[mxn],vis[mxn],dis[mxn];
- inline int read() {
- char c=getchar(); int x=0,f=1;
- while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
- while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
- return x*f;
- }
- inline void chkmax(register int &x,register int y) {if(x<y) x=y;}
- inline void chkmin(register int &x,register int y) {if(x>y) x=y;}
- struct ed {
- int to,nxt,w;
- }t[mxn<<1];
- inline void add(register int u,register int v,register int w) {
- t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
- }
- int getrt(register int u,register int fa) {
- f[u]=0; sz[u]=1;
- for(register int i=hd[u];i;i=t[i].nxt) {
- register int v=t[i].to;
- if(v==fa||vis[v]) continue ;
- getrt(v,u); sz[u]+=sz[v];
- chkmax(f[u],sz[v]);
- }
- chkmax(f[u],sumsz-sz[u]);
- if(f[rt]>f[u]) rt=u;
- }
- void getdis(register int u,register int fa) {
- if(dep[u]<=k) ++dis[dep[u]],ans+=bac[k-dep[u]];
- for(register int i=hd[u];i;i=t[i].nxt) {
- register int v=t[i].to;
- if(v==fa||vis[v]) continue ;
- dep[v]=dep[u]+t[i].w; getdis(v,u);
- }
- }
- void cal(register int u) {
- tot=0;
- for(register int i=hd[u];i;i=t[i].nxt) {
- register int v=t[i].to;
- if(vis[v]) continue ;
- dep[v]=t[i].w; getdis(v,u);
- for(register int j=1;j<=k;++j)
- bac[j]+=dis[j],dis[j]=0;
- }
- for(register int i=1;i<=k;++i) bac[i]=0;
- }
- void solve(register int u) {
- cal(u); vis[u]=1;
- for(register int i=hd[u];i;i=t[i].nxt) {
- register int v=t[i].to;
- if(vis[v]) continue ;
- rt=0; sumsz=sz[v];
- getrt(v,u); solve(rt);
- }
- }
- int main()
- {
- n=read(); k=read(); register int u,v,w; bac[0]=1;
- for(register int i=1;i<n;++i) {
- u=read(); v=read(); w=1;
- add(u,v,w); add(v,u,w);
- }
- rt=0; sumsz=f[0]=n;
- getrt(1,0); solve(rt);
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3004017.html