题面
设\(T\)为一棵有根树,我们做如下的定义:
- 设\(a\)和\(b\)为\(T\)中的两个不同节点。如果\(a\)是\(b\)的祖先,那么称“\(a\)比\(b\)不知道高明到哪里去了”。
- 设\(a\)和\(b\)为\(T\)中的两个不同节点。如果\(a\)与\(b\)在树上的距离不超过某个给定常数\(x\),那么称“\(a\)与\(b\)谈笑风生”。
给定一棵\(n\)个节点的有根树\(T\),节点的编号为\(1-n\),根节点为\(1\)号节点。你需要回答\(q\)个询问,询问给定两个整数\(p\) 和\(k\),问有多少个有序三元组\((a,b,c)\)满足:
- \(a,b\)和\(c\)为\(T\)中三个不同的点,且\(a\)为\(p\)号节点;
- \(a\)和\(b\)都比\(c\)不知道高明到哪里去了;
\(a\)和\(b\)谈笑风生。这里谈笑风生中的常数为给定的\(k\)。
解析
题面真有趣
有一个很套路的树状数组离线做法:(我在的博客里提过一遍)
按照中序遍历\(DFS\),每到一个点,先减去自己的子树以外的影响(树状数组询问一下),然后再把这个点加进树状数组。 这样当每个点的子树被遍历完时,用当前得到的答案,减去上一次得到的答案,就是自己的子树对答案的贡献。既然上次我写了线段树合并,这次就离线算法舒服一下:
(然后因树状数组内上限设为\(n\),\(GG\)了不知道多少回。。。)#include#include #include #include #include #include #include #define ll long long#define re register#define il inline#define pb(a) push_back(a)#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int N=3e5+100;int n,q,h[N],cnt,sz[N],d[N];ll t[N],ans[N];vector Q[N],id[N];struct Edge{int to,nxt;}e[N<<1];il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}il void mod(re int x,re int w){for(;x<=N-100;x+=x&-x) t[x]+=w;}il ll que(re int x){if(x>=N-100) x=N-100;re ll res=0;for(;x;x-=x&-x) res+=t[x];return res;}il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il void dfs(re int u,re int fa){ d[u]=d[fa]+1;sz[u]=1; for(re int i=0;i