锐客网

  1. 首页 > it技术 > >

[CF191](Fools|[CF191](Fools and Roads)

题意 : 给你一棵树，然后给你m对点，将每对点之间的最短路径上每条边权值+1，求操作完成后每条边的权值
solution:树上差分（其实如果你是数据结构大师的话也可以用树链剖分做）
【[CF191](Fools|[CF191](Fools and Roads)】树上差分的板子是这样的：
设差分数组p,对于路径s->t，p[s]++,p[t]++,p[lca(s,t)]--,p[fa[lca[(s,t)]]]--;
然后一个点的子树内差分数组值之和即为该点被覆盖的次数
然而这题要求我们处理边
那么我们有两种方法
一种是对于一条边，新建一个点代表这条边，由该点向边的两个端点连边
暴力但很无脑
另一种是用一条边的两个端点中深度较大的端点代表这条边
但此时原来的差分操作会出锅，要改为p[s]++,p[t]++,p[lca(s,t)]-=2（自己理解）
贴代码（第一种方法，欧拉序ST表求LCA）

#include #include #include #include #include #define N 400050 using namespace std; vector G[N]; int n,m; int dfn[N],pos[N],lg[N],dep[N]; int id[N],ans[N]; int st[35][N],cnt=0,plu[N],fa[N]; void aux(int x,int ff) { dfn[++cnt]=x,pos[x]=cnt,fa[x]=ff; for(int i=0; i>1]+1; for(int i=1; i<=cnt; i++)st[0][i]=dfn[i]; for(int i=1; i<=lg[cnt]; i++) for(int r=1; r+(1<y)swap(x,y); int p=lg[y-x+1]; return mn(st[p][x],st[p][y-(1<

转载于:https://www.cnblogs.com/stepsys/p/10802586.html

    推荐阅读


    上一篇：django|django 403问题

    下一篇：Collection集合中的Contains方法（包含不包含）