ToB企服应用市场:ToB评测及商务社交产业平台

标题: P4689 [Ynoi2016] 这是我自己的发明与 P5268 [SNOI2017] 一个简单的扣问0 [打印本页]

作者: 麻花痒 时间: 2024-8-18 15:08
标题: P4689 [Ynoi2016] 这是我自己的发明与 P5268 [SNOI2017] 一个简单的扣问0
思路：

首先可以先思量没有换根的环境。
先将树拍到 dfn 序上，那么一个子树 \(u\) 的所有点的 dfn 序区间为 \([dfn_u,dfn_u+siz_u-1]\)。
那么扣问变为：

每次给定两个区间 \([l_1,r_1],[l_2,r_2]\)，对于在第一个区间内的点 \(x\) 和在第二个区间的点 \(y\)，若 \((x,y)\) 有贡献，当且仅当 \(w_x=w_y\)。
扣问有贡献的点对数量。

即 P5268 [SNOI2017] 一个简单的扣问。
设 \(F(l_1,r_1,l_2,r_2)\) 体现 \([l_1,r_1]\) 与 \([l_2,r_2]\) 的贡献，那么：

\[F(l_1,r_1,l_2,r_2) = F(1,r_1,1,r_2) - F(1,l_1-1,1,r_2) - F(1,r_1,1,l_2-1) - F(1,l_1-1,1,l_2-1)\]
那么一个扣问就都转化为了四个 \(F(1,x,1,y)\) 的形式，思量如何求 \(F(1,x,1,y)\)，先钦定 \(x \le y\)，那么思量莫队：

设当前 \(p_{1,x},p_{2,x}\) 分别体现两个区间 \(x\) 的出现次数。
若 \(x \gets x+1\) 时，贡献会增长 \(p_{2,a_{x+1}}\)。
若 \(x \gets x-1\) 时，贡献会减少 \(p_{2,a_x}\)。
若 \(y \gets y+1\) 时，贡献会增长 \(p_{1,a_{y+1}}\)。
若 \(y \gets y-1\) 时，贡献会减少 \(p_{1,a_y}\)。

现在再思量换根操纵，若当前以 \(rt\) 为根：

若 \(rt\) 不在初始以 \(1\) 为根时 \(x\) 的子树内，则不好造成影响。
否则 \(x\) 子树内的点即为除了\((x \to rt)\) 路径上最接近 \(x\) 的点 \(y\) 子树内的点的全部点。

因为 \(x\) 在原始树上始终是 \(rt\) 的父亲，则 \(y\) 是 \(rt\) 的 \(dep_{rt}-dep_{x}-1\) 级祖先，直接倍增即可。
时间复杂度为 \(O(N\sqrt{M}+M \log N+M)\)。
完整代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=1e5+10,M=4e6+10,K=17;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)