html5网站源代码,手机如何建免费网站,wordpress文章编辑页面,discuz 修改网站标题正题 题目大意
求一棵树上有多少条路径长度≤len\leq len≤len 解题思路
首先普通点分治。扫描的时候将每个点保存为一个二元组(dis,gra)(dis,gra)(dis,gra)分别表示离(分治到的)根的距离#xff0c;属于根的那颗子树。
然后按照disdisdis排序#xff0c;两个指针L,RL,RL,…正题 题目大意
求一棵树上有多少条路径长度≤len\leq len≤len 解题思路
首先普通点分治。扫描的时候将每个点保存为一个二元组(dis,gra)(dis,gra)(dis,gra)分别表示离(分治到的)根的距离属于根的那颗子树。
然后按照disdisdis排序两个指针L,RL,RL,R用cnicn_icni表示[L1,R][L1,R][L1,R]这个区间内是iii这个子树的点的个数。
然后我们发现满足disLdisR≤lendis_Ldis_R\leq lendisLdisR≤len这个范围根据LLL的向前RRR是单调不升的然后两个指针维护一下每次统计一下答案R−L−cnLR-L-cn_LR−L−cnL codecodecode
#includecstdio
#includeset
#includealgorithm
using namespace std;
const int N100100;
struct node{int to,w,next;
}a[N*3];
struct Num_node{int a,b;
}num[N];
int siz[N],ls[N],v[N],root,len,n,f[N],ans,tot,x,y,w,cnt,cn[N];
bool cmp(Num_node x,Num_node y)
{return x.ay.a;}
void addl(int x,int y,int w)
{a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
void groot(int x,int fa)
{siz[x]1;f[x]0;for(int ils[x];i;ia[i].next)if(a[i].to!fa!v[a[i].to]){groot(a[i].to,x);siz[x]siz[a[i].to];f[x]max(f[x],siz[a[i].to]);}f[x]max(f[x],n-siz[x]);if (f[x]f[root]) rootx;
}
void dfs(int x,int fa,int w,int grafa)
{num[cnt].bgrafa;num[cnt].aw;cn[grafa];for(int ils[x];i;ia[i].next)if (!v[a[i].to]a[i].to!fa)cn[a[i].to]0,dfs(a[i].to,x,wa[i].w,grafa);
}
void dp(int x)
{v[x]1;cnt0;for(int ils[x];i;ia[i].next)if(!v[a[i].to])dfs(a[i].to,x,a[i].w,a[i].to);sort(num1,num1cnt,cmp);for(int L0,Rcnt;LR;L,cn[num[L].b]--){while(num[L].anum[R].alen) cn[num[R].b]--,R--;if(LR) break;ans(R-L-cn[num[L].b]);}for(int ils[x];i;ia[i].next)if(!v[a[i].to]){nsiz[a[i].to];root0;groot(a[i].to,0);dp(root);}
}
int main()
{scanf(%d%d,n,len);for(int i1;in;i){scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}f[0]2147483647;groot(1,0);dp(root);printf(%d,ans);
}
