昆山网站优化建设,零基础学做网站难吗,网站建设项目实践,国家企业信用信息查询平台P3899 [湖南集训]谈笑风生
题目描述
Solution
我们考虑离线询问#xff0c;将询问放在相对应的子树ppp中计算答案。
显然a,b,ca,b,ca,b,c的位置关系有两种情况#xff1a; bbb是aaa的祖先#xff0c;ccc是aaa的子孙。aaa是bbb的祖先#xff0c;ccc是bbb的子孙。
第一种…P3899 [湖南集训]谈笑风生
题目描述
Solution
我们考虑离线询问将询问放在相对应的子树ppp中计算答案。
显然a,b,ca,b,ca,b,c的位置关系有两种情况
bbb是aaa的祖先ccc是aaa的子孙。aaa是bbb的祖先ccc是bbb的子孙。
第一种位置关系很容易统计答案。 方案数为min(dep[a]−1,k)∗(size[a]−1)min(dep[a]-1,k)*(size[a]-1)min(dep[a]−1,k)∗(size[a]−1)。
第二种位置关系可以DSUontreeDSU\;on\;\;treeDSUontree或长链剖分计算。 显然DSUontreeDSU\;on\;\;treeDSUontree简单啊QAQQAQQAQ。
对于每一个bbb合法的ccc为bbb的子孙节点因此相当于每一个bbb的贡献为size[b]−1size[b]-1size[b]−1。我们在DSUontreeDSU\;on\;\;treeDSUontree的过程中记录一个值f[x]f[x]f[x]表示当前子树中深度为xxx的所有bbb的贡献和那么总答案就是每一个子树aaa的∑i1kf[dep[a]i]\sum_{i1}^{k}{f[dep[a]i]}∑i1kf[dep[a]i]。
相当于我们要支持单点修改区间求和用树状数组维护f[x]f[x]f[x]即可。
时间复杂度O(nlg2n)O(nlg^2n)O(nlg2n)但实测挺快的。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
vectorint e[MAXN];
vectorPR Q[MAXN];
int sz[MAXN],mx[MAXN],dep[MAXN],n,q;
ll sum[MAXN],Ans[MAXN];
int lowbit(int x){ return x(-x); }
void change(int x,ll y){ for (;xn;xlowbit(x)) sum[x]y; }
ll query(int x){ ll ans0; for (;x;x-lowbit(x)) anssum[x]; return ans; }
void dfs1(int x,int father)
{sz[x]1,mx[x]0,dep[x]dep[father]1;for (auto v:e[x]){if (vfather) continue;dfs1(v,x);sz[x]sz[v];if (sz[mx[x]]sz[v]) mx[x]v;}
}
void modify(int x,int c,int father,int mx)
{
// coutx dep[x]:c*(sz[x]-1)endl;change(dep[x],c*(sz[x]-1));for (auto v:e[x]){if (vfather||vmx) continue;modify(v,c,x,mx);}
}
void dfs2(int x,int father,int flag)
{for (auto v:e[x]){if (vfather||vmx[x]) continue;dfs2(v,x,0);}if (mx[x]) dfs2(mx[x],x,1);modify(x,1,father,mx[x]);for (auto y:Q[x]) {Ans[y.fi]query(min(n,dep[x]y.se))-query(dep[x])1ll*(min(y.se,dep[x]-1))*(sz[x]-1);
// couty.fi x y.se query(min(n,dep[x]y.se)) query(dep[x])endl;}if (!flag) modify(x,-1,father,0);
}
int main()
{nread(),qread();for (int i1;in;i){int uread(),vread();e[u].PB(v);e[v].PB(u);}for (int i1;iq;i) {int xread(),yread();Q[x].PB(MP(i,y));}dfs1(1,0);dfs2(1,0,1);for (int i1;iq;i) printf(%lld\n,Ans[i]);return 0;
}
