网站建设制作设计开发福建,网站开发文档撰写,深圳网页制作费用,专业做效果图网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
好久没写淀粉质了#xff0c;心血来潮复习一下。 淀粉质通常用来统计路径个数#xff0c;将路径分为子树内的和子树之间的。子树内的递归处理#xff0c;子树间的存下信息来每次都处理即…传送门
文章目录题意思路题意 思路
好久没写淀粉质了心血来潮复习一下。 淀粉质通常用来统计路径个数将路径分为子树内的和子树之间的。子树内的递归处理子树间的存下信息来每次都处理即可注意不要漏掉子树到根节点的贡献。 这个题要求不超过kkk的路径有多少条我们一个很容易想到的思路就是将每个子树到伪重心的距离都存下来每次与前面存下来的子树信息算一下答案。 这个实现起来复杂度很高每次计算答案需要遍历之前的子树这样就每一层的复杂度是O(n2)O(n^2)O(n2)级别的了显然不能接受。当然你可以使用一些黑科技维护一下但是没必要我们有更好的算法。 考虑一个容斥如果将所有路径都存下来排个序之后二分找答案这样算出来的答案可以发现不仅有两个子树之间的还有子树内部的所以我们在每次遍历完一个子树的时候将答案减去即可。 由于每一层需要排序复杂度O(nlognlogn)O(nlognlogn)O(nlognlogn)。
// Problem: 树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/254/
// Memory Limit: 10 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N10010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,k;
vectorPIIv[N];
vectorintq,qt;
bool st[N];int get_size(int u,int f) {if(st[u]) return 0;int ans1;for(auto x:v[u]) if(x.X!f) {ansget_size(x.X,u);}return ans;
}int get_wc(int u,int f,int tot,int wc) {if(st[u]) return 0;int sum1,mx0;for(auto x:v[u]) {if(x.Xf) continue;int nowget_wc(x.X,u,tot,wc);mxmax(mx,now); sumnow;}mxmax(mx,tot-sum);if(mxtot/2) wcu;return sum;
}void get_dis(int u,int f,int w) {if(st[u]) return;q.pb(w);for(auto x:v[u]) {if(x.Xf) continue;get_dis(x.X,u,wx.Y);}
}LL calc(int u) {if(st[u]) return 0;get_wc(u,-1,get_size(u,-1),u);LL ans0; st[u]true;for(auto x:v[u]) {get_dis(x.X,-1,x.Y);sort(q.begin(),q.end());for(int i0;iq.size();i) {int posupper_bound(q.begin(),q.end(),k-q[i])-q.begin();ans-min(pos,i1);qt.pb(q[i]); ansq[i]k;}q.clear();}sort(qt.begin(),qt.end());for(int i0;iqt.size();i) {int posupper_bound(qt.begin(),qt.end(),k-qt[i])-qt.begin(); ansmin(pos,i1);}qt.clear();for(auto x:v[u]) anscalc(x.X);return ans;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);while(scanf(%d%d,n,k)(nk)) {for(int i1;in-1;i) {int a,b,w; scanf(%d%d%d,a,b,w);v[a].pb({b,w}); v[b].pb({a,w});} printf(%lld\n,calc(0));for(int i0;in;i) v[i].clear(),st[i]0;}return 0;
}
/**/
