做购物网站需要多少钱,网站建设佰金手指科杰十一,上海百度搜索排名优化,软件代理文章目录题意#xff1a;题解#xff1a;树上差分代码#xff1a;树链剖分代码#xff1a;P3258 [JLOI2014]松鼠的新家题意#xff1a;
n个点#xff0c;n-1条边#xff0c;给出每个点的拜访顺序#xff0c;问每个点经过几次#xff08;最后一次移动不算拜访#xf…
文章目录题意题解树上差分代码树链剖分代码P3258 [JLOI2014]松鼠的新家题意
n个点n-1条边给出每个点的拜访顺序问每个点经过几次最后一次移动不算拜访
题解
题意明确后就很好做了对于给定的x和y我们只需要分别将x和y到lca(x,y)经过的点加一即可 但是这样直接做肯定不行 有两个方法
树上差分树链剖分
树上差分
参考题解 我们先考虑对于数组我们指定连续一段加一 我们现在对a2到a6区间进行加一 现在处理差分数组我们对a2加一对a7减一 差分属猪的定义:a[i] a[i-1] 差分数组[i] 也就是我们并没有改变区间的值而是改变的两个数之间的相对大小 对于树上差分 父亲节点u 其所有的子节点 他本身的差分数组 我们现在改变S到T边上所有点的值 我们对S的父亲节点减1对T加1
//把s-t路径上所有点均加w,
chafen[t] w;
chafen[s的父节点] - w; 当计算每个点具体值时 for(遍历与 u 相连的每一个子节点 v){num[u] num[v];
}
num[u] chafen[u];//加上差分数组 在本题中结合lca即可
代码
#include iostream
#include cstring
#include cstdio
#include algorithm
#include cmath
using namespace std;const int maxn 300050;
const int maxm maxn 1;
int N, M;
int a[maxn], t1, t2;
int head[maxn], cnt;struct Edge{int u, v, next;
}edge[maxm];inline void addedge(int u, int v){edge[cnt].u u;edge[cnt].v v;edge[cnt].next head[u];head[u] cnt;
}int fa[maxn][31], dep[maxn];void dfs(int u, int faa){fa[u][0] faa, dep[u] dep[faa] 1;for(int i 1; i 30; i){fa[u][i] fa[ fa[u][i - 1] ][i - 1];}for(int i head[u]; i ; i edge[i].next){int v edge[i].v;if(v faa)continue;dfs(v, u);}
} inline int lca(int x, int y){if(dep[x] dep[y])swap(x,y);for(int i 30; i 0; i--){if(dep[ fa[x][i] ] dep[y]) x fa[x][i];}if(x y)return x;for(int i 30; i 0; i--){if(fa[x][i] ! fa[y][i]){x fa[x][i], y fa[y][i];}}return fa[x][0];
}int num[maxn];int answer(int u, int faa){for(int i head[u]; i ; i edge[i].next){int v edge[i].v;if(v faa)continue;answer(v, u);num[u] num[v];}
}
int main(){cinN;for(int i 1; i N; i){cin a[i];}for(int i 1; i N; i){cin t1 t2;addedge(t1, t2);addedge(t2, t1);}dfs(1, 0);for(int i 1; i N - 1; i){int u a[i], v a[i 1];int t lca(u, v);num[ fa[t][0] ] - 1;num[ t ] - 1;num[ u ] 1;num[ v ] 1;}answer(1,0);for(int i 2; i N; i){num[a[i]]--;}for(int i 1; i N; i){coutnum[i]endl;}
}树链剖分
树链剖分就直接进行区间修改加一就行哈
代码
这个代码我调了半个晚上哭了哭了终于调好了
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e69;
int a[maxn];
struct node{int u,v,next;
}edge[maxn];
int cnt0;
int tot0;
int n;
int head[maxn];
void add(int u,int v)
{edge[cnt].vv;edge[cnt].nexthead[u];head[u]cnt;
}
//---
int tr[maxn2],laz[maxn2];
inline void pushup(int rt)
{tr[rt]tr[rt1]tr[rt1|1];
}
inline void pushdown(int rt,int l,int r)
{int len(r-l1);laz[rt1]laz[rt];laz[rt1|1]laz[rt];tr[rt1]laz[rt]*(len-(len1));tr[rt1|1]laz[rt]*(len1);laz[rt]0;
}
inline void build(int rt,int l,int r)
{if(lr){tr[rt]0;return ;}int midlr1; build(rt1,l,mid);build(rt1|1,mid1,r);pushup(rt);
}
inline int query(int rt,int l,int r,int ip)
{if(liprip)return tr[rt];if(laz[rt])pushdown(rt,l,r);int midlr1;int ress0;if(ipmid)ressquery(rt1,l,mid,ip);if(ipmid)ressquery(rt1|1,mid1,r,ip);return ress;
}
inline void update(int rt,int l,int r,int L,int R,int k)
{if(LlrR){int len(r-l1);laz[rt]k;tr[rt]k*len;}else {if(laz[rt])pushdown(rt,l,r);int midlr1;if(Lmid)update(rt1,l,mid,L,R,k);if(Rmid)update(rt1|1,mid1,r,L,R,k);pushup(rt);}
}
//---
int fa[maxn],dep[maxn],siz[maxn],id[maxn],top[maxn],son[maxn];
inline int updrange(int x,int y,int k)
{while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);update(1,1,n,id[top[x]],id[x],k);xfa[top[x]];}if(dep[x]dep[y])swap(x,y);update(1,1,n,id[x],id[y],k);
}
inline void dfs1(int x,int f,int deep)
{dep[x]deep;fa[x]f;siz[x]1;int maxson-1;for(int ihead[x];i;iedge[i].next){int vedge[i].v;if(vf)continue;dfs1(v,x,deep1);siz[x]siz[v];if(siz[v]maxson){son[x]v;maxsonsiz[v];}}
}
inline void dfs2(int x,int topf)
{id[x]tot;top[x]topf;if(!son[x])return ;dfs2(son[x],topf);for(int ihead[x];i;iedge[i].next){int vedge[i].v;if(vfa[x]||vson[x])continue;dfs2(v,v);}
}
void print()
{for(int i1;in;i){printf(%d\n,query(1,1,n,id[i]));//coutendl;}
// printf(----\n);
}
int main()
{cinn;for(int i1;in;i)cina[i];for(int i1;in;i){int x,y;cinxy;add(x,y);add(y,x);}dfs1(a[n],0,1);dfs2(a[n],a[n]);build(1,1,n);updrange(a[1],a[1],1);//print();for(int i1;in;i){updrange(a[i],a[i1],1);updrange(a[i],a[i],-1);// print();}updrange(a[n],a[n],-1);print();return 0;
}
