P4689 [Ynoi2016] 这是我自己的发明 与 P5268 [SNOI2017] 一个简单的询问0
思路：首先可以先考虑没有换根的情况。
先将树拍到 dfn 序上，那么一个子树 \(u\) 的所有点的 dfn 序区间为 \(\)。
那么询问变为：
[*]每次给定两个区间 \(,\)，对于在第一个区间内的点 \(x\) 和在第二个区间的点 \(y\)，若 \((x,y)\) 有贡献，当且仅当 \(w_x=w_y\)。
[*]询问有贡献的点对数量。
即 P5268 一个简单的询问。
设 \(F(l_1,r_1,l_2,r_2)\) 表示 \(\) 与 \(\) 的贡献，那么：
\
那么一个询问就都转化为了四个 \(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)\)。
完整代码：
#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
页:
[1]