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