以为裸点分治,但数据范围怎么这么小?快打完了发现不对。。
n^2做的话其实是个水题。。
枚举每一个点为根,为了不重复计算,我们要求所求的三个点必须分别位于三棵子树上。 考虑当前前3棵子树深度为deep的点分别有a,b,c个,新增的子树深度为deep的点有d个,那么新加的答案为:\[dab+dac+dbc=[ab+(a+b)c]*d\] 同理第5棵子树同一深度的点数为e,新加答案:\[...=[ab+(a+b)c+(a+b+c)d]*e\] 那么第6棵子树新加的答案应为:\[...=[ab+(a+b)c+(a+b+c)d+(a+b+c+d)e]*f\] (以下sz表示每棵子树中处于某一深度的点数)于是我们可以求每棵子树某一深度的点数,每次答案先加上当前 \(sz*[]里的式子\),再维护[]里的整个式子,即加上 \(sz*先前的子树和\),再更新子树的和(\(a+b+c...+=sz\))。
更好的方式是直接从组合理解,即答案加上当前子树乘上之前的子树中选两个的方案数,然后更新选两个的方案数,即 \(当前子树sz*之前子树选一个的方案数\),再更新子树中选一个的方案数,就是加上sz.长链剖分:。
//976kb 4808ms#include#include #include #include #define gc() getchar()const int N=5005;int n,Enum,Maxd,H[N],nxt[N<<1],to[N<<1],c1[N],c2[N],sum[N];long long Ans;inline int read(){ int now=0;register char c=gc(); for(;!isdigit(c);c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now;}inline void AddEdge(int u,int v){ to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum; to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum; }void DFS(int x,int f,int d){ ++sum[d], Maxd=std::max(Maxd,d); for(int i=H[x]; i; i=nxt[i]) if(to[i]!=f) DFS(to[i],x,d+1);}int main(){ n=read(); for(int u,v,i=1; i