超级神秘缝合怪（？）
题意
给定 \(n\) 个点的有根树，\(q\) 次询问 \(l,r,x\) 表示求 \([l,r]\) 中有多少无序点对 \((i,j)\) 满足 \(l\le i<j\le r\) 且 \(\operatorname{lca}(i,j)=x\)。
\(n,q\le 2\times10^5,128\text{MB}\)
分析
考虑答案即为 \(\dbinom{cnt_x}{2}-\dbinom{cnt_{son_{x,1}}}{2}-\dbinom{cnt_{son_{x,2}}}{2}-\cdots-\dbinom{cnt_{son_{x,k}}}{2}\)，其中 \(cnt_x\) 表示 \(x\) 子树内编号在 \([l,r]\) 内的点个数，套上 dfn 序就转化成了 \((i,dfn_i)\) 做二维数点，但是造个菊花就平方了。考虑根号分治，度数 \(\le B\) 的做上述暴力，直接做是 \(O(n\sqrt n\log n)\) 的，考虑到 \(O(n)\) 次修改和 \(O(n\sqrt n)\) 次查询，根号平衡一下即可。由于二维数点要离线扫描线，需要做一个差分，而原本我们是要记录每个询问上的答案的，这样空间复杂度就 \(O(n\sqrt n)\) 然后爆掉了。由于这一块常数本身就很大了，询问分成 \(b\) 块做虽然空间能卡进去但是时间炸了。考虑到那些儿子的 dfn 询问区间是连续的，考虑扫 dfn 维，那么第 \(i\) 个儿子的答案就是当前儿子末尾的询问结果减去前一个儿子的末尾的询问结果，直接对每个询问开一个临时数组存当前询问最后一个儿子末尾的询问结果即可，别忘了询问完把当前的 vector 彻底清空，这样空间复杂度才是 \(O(n)\) 的。
考虑度数 \(>B\) 怎么做，这样的点不会超过 \(O(\frac{n}{B})\)。此时我们考虑对前 \(B\) 个儿子按照上面做，对于剩下的儿子，我们将每个子树染上子树根的颜色，然后做小 Z 的袜子。这样做的复杂度为啥是对的呢？考虑每个点会被染几次，显然一个点每被染一次子树大小就 \(\times B^2\)（子树本身 \(\times B\)，还有 \(B\) 个大小不小于该子树的），所以每个点的总贡献就是 \(O(n)\) 了。
总时间复杂度 \(O(n\sqrt n)\)，不能通过（不卡常还想过 Ynoi？）。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<array>
#include<tuple>
#include<ctime>
#include<random>
#include<cassert>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define j0 jj0
#define j1 jj1
#define y0 yy0
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0)
#define OTIE cout.tie(0)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define popc __builtin_popcountll
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using namespace __gnu_pbds;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline bool ckmx(T1 &qwqx,T2 qwqy){return qwqx>=qwqy?0:(qwqx=qwqy,1);}
template<typename T1,typename T2>inline bool ckmn(T1 &qwqx,T2 qwqy){return qwqx<=qwqy?0:(qwqx=qwqy,1);}
inline auto rd(){int qwqx=0,qwqf=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')qwqf=-1;ch=getchar();}while(ch>='0'&&ch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+ch-48;ch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char ch='\n'){if(qwqx<0){qwqx=-qwqx;putchar('-');}int qwqy=0;static char qwqz[40];while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}while(qwqy--){putchar(qwqz[qwqy]);}if(ch)putchar(ch);
}
bool Mbg;
const int mod=998244353;
template<typename T1,typename T2>inline void adder(T1 &x,T2 y){x+=y,x=x>=mod?x-mod:x;}
template<typename T1,typename T2>inline void suber(T1 &x,T2 y){x-=y,x=x<0?x+mod:x;}
const int maxn=2e5+5,maxm=455,inf=0x3f3f3f3f,B=450,D=50;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,Q,rt;
struct query{int l,r,x;i64 ans;
}q[maxn];
vector<int>_G[maxn],G[maxn];
int dfn[maxn],siz[maxn],dfncnt,fa[maxn],nfd[maxn];
void dfs0(int x,int y){siz[x]=1,fa[x]=y;for(int u:_G[x])if(u^y)G[x].pb(u),dfs0(u,x),siz[x]+=siz[u];
}
void dfs1(int x){dfn[x]=++dfncnt,nfd[dfncnt]=x;for(int u:G[x])dfs1(u);
}
il i64 calc(i64 x){return x*(x-1)/2;}
il int bel(int x){return (x-1)/B+1;}
struct DS{il int R(int x){return min(n,x*B);}int sa[maxn],sb[maxm],num;void init(){mem(sa,0),mem(sb,0);}il void add(int x,int val){rep(i,x,R(bel(x)))sa[i]+=val;rep(i,bel(x),num)sb[i]+=val;}il int qry(int x){if(!x)return 0;return sb[bel(x)-1]+sa[x];}il int qry(int l,int r){return qry(r)-qry(l-1);}
} ds;
vector<pii>vec[maxn],wec[maxn];
vector<int>col[maxn];
struct query2{int l,r,id;bool operator<(const query2 &p)const{if(bel(l)^bel(p.l))return bel(l)<bel(p.l);return bel(l)&1?r<p.r:r>p.r;}
}q2[maxn];
i64 qwq[maxn];
int cnt[maxn];
il void add(int x){for(int u:col[x])qwq[fa[u]]+=cnt[u],cnt[u]++;
}
il void del(int x){for(int u:col[x])cnt[u]--,qwq[fa[u]]-=cnt[u];
}
int lst[maxn];
bool vis[maxn];
int tmp[maxn];
inline void solve_the_problem(){n=rd(),Q=rd(),rt=rd(),ds.num=(n-1)/B+1;rep(i,2,n){int x=rd(),y=rd();_G[x].pb(y),_G[y].pb(x);}rep(i,1,Q)q[i].l=rd(),q[i].r=rd(),q[i].x=rd();dfs0(rt,0);rep(i,1,n)sort(all(G[i]),[](int x,int y){return siz[x]>siz[y];});dfs1(rt);rep(i,1,n)wec[dfn[q[i].x]-1].pb(mp(i,-1)),wec[dfn[q[i].x]+siz[q[i].x]-1].pb(mp(i,1));rep(i,1,Q){int x=q[i].x;int ed=(int)G[x].size()<=D?dfn[x]+siz[x]:dfn[G[x][D]];vec[dfn[x]].pb(mp(i,ed));}mem(lst,-1);nfd[n+1]=n+1,siz[n+1]=n+1;rep(i,1,n){ds.add(nfd[i],1);for(pii _:wec[i]){int id=_.fi,fir=_.se;tmp[id]+=fir*ds.qry(q[id].l,q[id].r);}for(pii _:vec[i]){int id=_.fi,ed=_.se,nxt=i+siz[nfd[i+1]],nw=ds.qry(q[id].l,q[id].r);if(~lst[id])q[id].ans-=calc(nw-lst[id]);lst[id]=nw;if(nxt<ed)vec[nxt].pb(_);}vec[i].clear(),vec[i].shrink_to_fit();}rep(i,1,Q)q[i].ans+=calc(tmp[i]);int Q2=0;rep(i,1,Q){int x=q[i].x;if((int)G[x].size()>D){q2[++Q2].l=q[i].l,q2[Q2].r=q[i].r,q2[Q2].id=i;if(vis[x])continue;vis[x]=1;rep(j,D,(int)G[x].size()-1){int u=G[x][j];rep(id,dfn[u],dfn[u]+siz[u]-1)col[nfd[id]].pb(u);}}}sort(q2+1,q2+Q2+1);int ql=1,qr=0;rep(i,1,Q2){int l=q2[i].l,r=q2[i].r,id=q2[i].id;while(l<ql)add(--ql);while(qr<r)add(++qr);while(ql<l)del(ql++);while(r<qr)del(qr--);q[id].ans-=qwq[q[id].x];}rep(i,1,Q)write(q[i].ans);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);int _=1;while(_--)solve_the_problem();
}
/**/