Description
给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于KInput
N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是kOutput
一行,有多少对点之间的距离小于等于kSample Input
7 1 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2 10Sample Output
5前置知识:
后置知识:还能有啥后置知识,处理过程中sort+two point扫描即可
/*program from Wolfycz*/#include#include #include #include #include #define inf 0x7f7f7f7f#define sqr(x) ((x)*(x))using namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline char gc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int frd(){ int x=0,f=1;char ch=gc(); for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0'; return x*f;}inline int read(){ int x=0,f=1;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0'; return x*f;}inline void print(int x){ if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0');}const int N=4e4;int pre[(N<<1)+10],now[N+10],child[(N<<1)+10],val[(N<<1)+10];int size[N+10],dis[N+10],h[N+10];bool vis[N+10];int tot,Max,root,K,top;ll Ans;void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}void Get_root(int x,int fa,int sz){ int res=0; size[x]=1; for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){ if (son==fa||vis[son]) continue; Get_root(son,x,sz); size[x]+=size[son]; res=max(res,size[son]); } res=max(res,sz-size[x]); if (res K) r--; res+=r-l+1; } return res;}void divide(int x){ vis[x]=1,Ans+=solve(x,0); for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){ if (vis[son]) continue; Ans-=solve(son,val[p]); Max=inf,root=0; Get_root(son,0,size[son]); divide(root); }}int main(){ int n=read(); for (int i=1;i