上海网站优化上,国内 wordpress主题,一个ip地址做多个网站,淄博网站建设卓迅模板题 P3806 【模板】点分治1
题目描述
给定一棵有 n 个点的树#xff0c;询问树上距离为 k 的点对是否存在。
详讲
关于点分治具体内容可以看这个 这里主要是详细讲讲代码#xff1a; getrt是用来求重心#xff0c;我们利用树型dp的思维来做#xff0c;即找到该节点所…模板题 P3806 【模板】点分治1
题目描述
给定一棵有 n 个点的树询问树上距离为 k 的点对是否存在。
详讲
关于点分治具体内容可以看这个 这里主要是详细讲讲代码 getrt是用来求重心我们利用树型dp的思维来做即找到该节点所有的子树找到最大的哪一颗即可
void getrt(int u,int pa)//求重心
{size[u]1; maxp[u]0;for(int ihead[u];i;iE[i].nxt) {int vE[i].v;if(vpa||vis[v]) continue;getrt(v,u);size[u]size[v];maxp[u]max(maxp[u],size[v]);}maxp[u]max(maxp[u],sum-size[u]);if(maxp[u]maxp[rt]) rtu;
}
getdis是用来求每一个子节点到根的距离 getdis在calc中不断被调用
void getdis(int u,int fa)//每一个子节点到根的距离
{rem[rem[0]]dis[u];for(int ihead[u];i;iE[i].nxt){int vE[i].v;if(vfa||vis[v])continue;dis[v]dis[u]E[i].dis;getdis(v,u);}
}calc是用来合并答案的因为在getdis中已经计算出所有点到根的距离所以把任意两个出现的距离凑在一起并】、判断可否凑出我们需要的k即可 rem[i]存的是在getdis中求出的距离rem[0]这个值是值rem存了多少值 judge我们可以用来存距离对已经出现的距离用judge标记为1这样当出现另一个距离可以和这个距离搭配成我们所需的k时就可以直接标记答案 judge[query[k]-rem[j]]; query[k]-rem[j]即为所需要的距离
test[k]|judge[query[k]-rem[j]]; 用|就可以实现如果有就给test标记
void calc(int u)
{int p0;for(int ihead[u];i;iE[i].nxt){int vE[i].v;if(vis[v])continue;rem[0]0; dis[v]E[i].dis;getdis(v,u);//处理u的每个子树的disfor(int jrem[0];j;--j)//遍历当前子树的disfor(int k1;km;k)//遍历每个询问{if(query[k]rem[j])test[k]|judge[query[k]-rem[j]];//如果query[k]-rem[j]的路径存在就标记第k个询问}for(int jrem[0];j;--j)//保存出现过的dis于judge{q[p]rem[j];judge[rem[j]]1;}}for(int i1;ip;i)//处理完这个子树就清空judgejudge[q[i]]0;//特别注意一定不要用memeset会T}solve则是对每一个根进行处理通过solve来调用上述函数在递归过程中不断重复一样的过程
void solve(int u)
{ //judge[i]表示到根距离为i的路径是否存在vis[u]judge[0]1;calc(u);//处理以u为根的子树for(int ihead[u];i;iE[i].nxt)//对每个子树进行分治{int vE[i].v;if(vis[v])continue;sumsize[v]; maxp[rt0]inf;//注意sum是以v为根的子树大小getrt(v,0);solve(rt);//在子树中找重心并递归处理}
}代码
//niiick
#includeiostream
#includevector
#includealgorithm
#includequeue
#includecstring
#includecstdio
using namespace std;int read()
{int f1,x0;char ssgetchar();while(ss0||ss9){if(ss-)f-1;ssgetchar();}while(ss0ss9){xx*10ss-0;ssgetchar();}return f*x;
}const int inf10000000;
const int maxn100010;
int n,m;
struct node{int v,dis,nxt;}E[maxn1];
int tot,head[maxn];
int maxp[maxn],size[maxn],dis[maxn],rem[maxn];
int vis[maxn],test[inf],judge[inf],q[maxn];
int query[1010];
int sum,rt;
int ans;void add(int u,int v,int dis)
{E[tot].nxthead[u];E[tot].vv;E[tot].disdis;head[u]tot;
}void getrt(int u,int pa)//求重心
{size[u]1; maxp[u]0;for(int ihead[u];i;iE[i].nxt) {int vE[i].v;if(vpa||vis[v]) continue;getrt(v,u);size[u]size[v];maxp[u]max(maxp[u],size[v]);}maxp[u]max(maxp[u],sum-size[u]);if(maxp[u]maxp[rt]) rtu;
}void getdis(int u,int fa)//每一个子节点到根的距离
{rem[rem[0]]dis[u];for(int ihead[u];i;iE[i].nxt){int vE[i].v;if(vfa||vis[v])continue;dis[v]dis[u]E[i].dis;getdis(v,u);}
}void calc(int u)
{int p0;for(int ihead[u];i;iE[i].nxt){int vE[i].v;if(vis[v])continue;rem[0]0; dis[v]E[i].dis;getdis(v,u);//处理u的每个子树的disfor(int jrem[0];j;--j)//遍历当前子树的disfor(int k1;km;k)//遍历每个询问{if(query[k]rem[j])test[k]|judge[query[k]-rem[j]];//如果query[k]-rem[j]的路径存在就标记第k个询问}for(int jrem[0];j;--j)//保存出现过的dis于judge{q[p]rem[j];judge[rem[j]]1;}}for(int i1;ip;i)//处理完这个子树就清空judgejudge[q[i]]0;//特别注意一定不要用memeset会T}void solve(int u)
{ //judge[i]表示到根距离为i的路径是否存在vis[u]judge[0]1; calc(u);//处理以u为根的子树for(int ihead[u];i;iE[i].nxt)//对每个子树进行分治{int vE[i].v;if(vis[v])continue;sumsize[v]; maxp[rt0]inf;//注意sum是以v为根的子树大小getrt(v,0); solve(rt);//在子树中找重心并递归处理}
}int main()
{nread();mread();for(int i1;in;i){int uread(),vread(),disread();add(u,v,dis);add(v,u,dis);}for(int i1;im;i)query[i]read();//先记录每个询问以离线处理maxp[rt]sumn;//第一次先找整棵树的重心getrt(1,0); solve(rt);//对树进行点分治for(int i1;im;i){if(test[i]) printf(AYE\n);else printf(NAY\n);}return 0;
}代码2
//#pragma optimize(Ofast)
#includebits/stdc.h
#define MAXN 10005
#define MAXK 10000007
#define inf int(16843009)
using namespace std;
typedef long long ll;int N,M,K[MAXN];
struct edge{int v,w;edge(int v0, int w0):v(v), w(w){}
};vectoredge adj[MAXN];int vis[MAXN],d[MAXN],sz[MAXN];
int rt,cnt;void dfs_rt(int u, int fa, int tot){//cnt;sz[u] 1;int v,w,n0;for(int k0;kadj[u].size();k){v adj[u][k].v;if(vfa || vis[v]) continue;dfs_rt(v,u,tot);sz[u] sz[v];n max(n, sz[v]);}n max(n, tot-sz[u]);if(2*n tot) rt u;
}bool t[MAXK], ans[MAXN]; void dfs1(int u, int fa){cnt;for(int i1;iM;i){if(d[u] K[i]) ans[i] | t[K[i] - d[u]];}int v,w;for(int k0;kadj[u].size();k){v adj[u][k].v; w adj[u][k].w;if(vfa || vis[v]) continue;d[v] d[u] w;dfs1(v,u);}
}void dfs2(int u, int fa, int flag){for(int i1;iM;i){if(d[u] K[i]){if(flag1) t[d[u]] 1;else t[d[u]] 0;}}int v;for(int k0;kadj[u].size();k){v adj[u][k].v;if(vfa || vis[v]) continue;dfs2(v,u,flag);}
}void work(int u, int fa, int tot){dfs_rt(u,fa,tot);u rt;vis[u] 1; d[u] 0;t[0] 1;int v,w;for(int k0;kadj[u].size();k){v adj[u][k].v; w adj[u][k].w;if(vis[v]) continue;cnt 0;d[v] w;dfs1(v,u);sz[v] cnt;dfs2(v,u,1);}dfs2(u,0,-1);for(int k0;kadj[u].size();k){v adj[u][k].v;if(vis[v]) continue;work(v,u,sz[v]);}
}int main(){scanf(%d%d, N, M);int u,v,w;for(int i1;iN;i){scanf(%d%d%d, u, v, w);adj[u].push_back(edge(v,w));adj[v].push_back(edge(u,w));}for(int i1;iM;i){scanf(%d, K[i]);}t[0] 1;work(1,0,N);for(int i1;iM;i){if(ans[i]) puts(AYE);else puts(NAY);}return 0;
}
