本文共 2190 字，大约阅读时间需要 7 分钟。
第一次写树分治、找重心，还是不太理解
hzwer:
考虑经过根的路径，依次处理其子树，维护平衡树.
对于第S棵子树其每个结点x，在平衡树中查询出发点为根，终点在S-1子树中，小于K-dis[x]+1的路径数量num，ans+=num
再用S更新平衡树
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--) 14 #define re(i,l,r) for(int i=(l);i<=(r);i++) 15 #define Clear(a,b) memset(a,b,sizeof(a)) 16 #define inout(x) printf("%d",(x)) 17 #define douin(x) scanf("%lf",&x) 18 #define strin(x) scanf("%s",(x)) 19 #define LLin(x) scanf("%lld",&x) 20 #define op operator 21 #define CSC main 22 typedef unsigned long long ULL; 23 typedef const int cint; 24 typedef long long LL; 25 using namespace std; 26 void inin(int &ret) 27 { 28 ret=0;int f=0;char ch=getchar(); 29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();} 30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar(); 31 ret=f?-ret:ret; 32 } 33 struct treap 34 { 35 int ed,root; 36 int ch[40040][2],w[40040],c[40040],s[40040],r[40040]; 37 void inin(){ed=root=0;} 38 void maintain(int k){ if(k)s[k]=c[k]+s[ch[k][0]]+s[ch[k][1]];} 39 void rotate(int &k,int d){ int p=ch[k][d^1];ch[k][d^1]=ch[p][d];ch[p][d]=k;maintain(k);maintain(p),k=p;} 40 void add(int &k,int x) 41 { 42 if(!k){k=++ed,w[k]=x,c[k]=s[k]=1,r[k]=rand(),ch[k][0]=ch[k][1]=0;return ;} 43 s[k]++; 44 if(w[k]==x){c[k]++;return ;} 45 int d=x>w[k]; 46 add(ch[k][d],x); 47 if(r[ch[k][d]] x)return query(ch[k][0],x); 54 return s[ch[k][0]]+c[k]+query(ch[k][1],x); 55 } 56 }t; 57 int n,head[40040],next[80080],zhi[80080],w[80080],ans,ed,k,sum,root; 58 void add(int a,int b,int c) 59 { 60 next[++ed]=head[a],head[a]=ed,zhi[ed]=b,w[ed]=c; 61 next[++ed]=head[b],head[b]=ed,zhi[ed]=a,w[ed]=c; 62 } 63 bool bo[40040]; 64 int f[40040],s[40040],temp[40040],dis[40040]; 65 void getroot(int x,int fa) 66 { 67 f[x]=0;s[x]=1; 68 for(int i=head[x];i;i=next[i])if(zhi[i]!=fa&&!bo[zhi[i]]) 69 { 70 getroot(zhi[i],x); 71 s[x]+=s[zhi[i]]; 72 f[x]=max(f[x],s[zhi[i]]); 73 } 74 f[x]=max(f[x],sum-s[x]); 75 if(f[x]
转载于:https://www.cnblogs.com/HugeGun/p/5153574.html