sjwhsss @ 2024-11-25 20:30:48
为什么我自己写的线段树合并计算终点的贡献用
Insert(rt[y] , 1 , n<<1 , dep[x] - dep[lca] * 2 + n , 1);
Insert(rt[fa[lca]] , 1 , n<<1 , dep[x] - dep[lca] * 2 + n , -1);
和
ans[u]+=Query(rt[u] , 1 , n<<1 , w[u] - dep[u] + n);
就过不了样例二,而用题解的
Insert(rt[y] , 1 , n<<1 , n + dep[lca] * 2 - dep[x] , 1);
Insert(rt[fa[lca]] , 1 , n<<1 , n + dep[lca] * 2 - dep[x] , -1);
和
ans[u]+=Query(rt[u] , 1 , n<<1 , dep[u] - w[u] + n);
就能过,两个写法不是等价的吗?
by D_FANG @ 2024-12-09 16:53:40
@sjwhsss 可能……也许……大概……,在您的
dep[x] - dep[lca] * 2 + n
当树成一条链,lca为链末端时,这条式子好像会为0,但您的线段树的值域却是从1开始(但这好像和你过不了样例2没啥练习
by D_FANG @ 2024-12-09 16:54:10
说错了,是联系