树套树Day2暂且搁置...因为Day1的题我各种不会做...
唯一过了一道还是整体二分过的...
我们来一点愉快的算法，先不考虑数据结构这种骚东西了
毕竟还在发烧，就先码码这几天在搞的点分治吧
hx你又挖一个大坑赶紧去填树套树
点分治用于解决“树上路径点权统计问题”
...讲不太清楚，大家可以直接看题
点分治的思想呢，就是我们在树上走路径的时候，对于一个点，有两种方案：
1.选
2.不选
如果“不选”一个点，我们可以知道我们也会“不选”他的子树，递归处理即可
如果选一个点，有一个特别重要的性质：
如果一条路径要经过这个点,那么他必然是由两条在这个点不同子树中到这个点的路径组合而成
然后我们面临两条选择
1.直接dfs做
2.“动态点分治”(Orz popoqqq大爷)
由于是Day1...
我们来讲讲dfs!
我们知道，树这个东西是递归定义的，所以我们处理一棵树相当于处理它的根节点，然后递归处理它的每个子树
现在我们面临一个问题：根节点可以是任意的，我们怎么选根节点呢
考虑贪心的思想：让递归层数最小
我们每次选出的根节点要让这棵树的“总深度”最小
大概就是这样的
void getroot(int v,int fa) { son[v] = 1; f[v] = 0;//f记录以v为根的最大子树的大小 for(int i = head[v];i;i=e[i].next) if(e[i].to != fa && !vis[e[i].to]) { getroot(e[i].to,v);//递归更新 son[v] += son[e[i].to]; f[v] = max(f[v],son[e[i].to]);//比较每个子树 } f[v] = max(f[v],sum-son[v]);//别忘了以v父节点为根的子树 if(f[v] < f[root]) root = v;//更新当前根 }
理解了这个思想，我们就可以看一下下面的例题：
poj1741
给一颗n个节点的树，每条边上有一个距离v（v<=1000）。定义d(u,v)为u到v的最小距离。给定k值，求有多少点对（u，v）使u到v的距离小于等于k。数据范围：n<=10000,k<2^31
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #include<algorithm> using namespace std; #define INF 0x7fffffff struct node{int y,v,next;}e[20010]; int n,len,k,root,sum,ans,Link[10010],f[10010],vis[10010],son[10010],d[10010],deep[10010]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y,int v) { e[++len].next=Link[x]; Link[x]=len; e[len].v=v; e[len].y=y; } void getroot(int x,int fa) { son[x]=1; f[x]=0; for(int i=Link[x];i;i=e[i].next) { if(e[i].y==fa||vis[e[i].y]) continue; getroot(e[i].y,x); son[x]+=son[e[i].y]; f[x]=max(f[x],son[e[i].y]); } f[x]=max(f[x],sum-son[x]); if(f[x]<f[root]) root=x; } void getdeep(int x,int fa) { deep[++deep[0]]=d[x]; for(int i=Link[x];i;i=e[i].next) { if(e[i].y==fa||vis[e[i].y]) continue; d[e[i].y]=d[x]+e[i].v; getdeep(e[i].y,x); } } int cal(int x,int v) { d[x]=v; deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); int l=1,r=deep[0],sum=0; while(l<r) { if(deep[l]+deep[r]<=k) {sum+=r-l; l++;} else r--; } return sum; } void solve(int x) { ans+=cal(x,0);//计算答案 vis[x]=1; for(int i=Link[x];i;i=e[i].next) { if(vis[e[i].y]) continue; ans-=cal(e[i].y,e[i].v);//计算不符合题意的答案 sum=son[e[i].y]; root=0; getroot(e[i].y,0); solve(root); } } int main() { freopen("cin.in","r",stdin); freopen("cout.out","w",stdout); while(1) { ans=0,root=0,len=0; memset(vis,0,sizeof(vis)); memset(Link,0,sizeof(Link)); n=read(); k=read(); if(n==0&&k==0) break; for(int i=1;i<=n-1;i++) { int x=read(),y=read(),v=read(); insert(x,y,v); insert(y,x,v); } f[0]=INF; sum=n; getroot(1,0); solve(root); printf("%d ",ans); } return 0; }
题解：对于每个点记录子树中出现的距离值，对于一棵树的距离值数组，把它排序求一次ans1，再对每棵子树分别求一个自己对自己的ans2，ans1-Σans2即为最后的ans。
例题：
bzoj2599
poj1741
bzoj2152
这回有完整代码了...
明天更树套树Day2
近期要更的：
树套树Day2
数据结构综合刷题Day1
FFT&NTT综合刷题(这个不知道要几天...)
矩阵练习.pdf(我真是日了...)
杜教筛刷题
莫比乌斯反演刷题
点分治Day2
CDQ分治&整体二分