论我到底学了多少假算法
emm大概开始复习吧（？）整理了一下发现我有些算法可能几个世纪没碰了...得回来看看了QAQ
————————————分个鸽————————————
点分治，顾名思义，就是分治。。。
每次我们找到树的重心，统计答案，分治子树继续找重心统计答案。一般这类题是树上计数（？）
因为我太弱了所以我只列举了两种点分治的方法。
我们以洛咕4178为例
一、类似容斥
我们这个题要求的是距离小于等于k的点对个数，很显然可以统计当前节点x子树内的答案然后-两个点对位于相同子树内（就是共享了一条边到达x的）。我们可以求出子树内每个点到x的距离，然后排个序，用双指针扫一下统计答案就行了。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 40010
using namespace std;
struct edge{int to,lt,v;}e[maxn<<1];
int in[maxn],cnt;bool vis[maxn];
int dis[maxn],sz[maxn],mxs[maxn];
int rt,tot,a[maxn],cur,k,final;
void add(int x,int y,int v)
{
e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].v=v;in[x]=cnt;
e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].v=v;in[y]=cnt;
}
void dfs(int x,int fa)
{
sz[x]=1;mxs[x]=0;
for(int i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
dfs(v,x);sz[x]+=sz[v];mxs[x]=max(mxs[x],sz[v]);
}
mxs[x]=max(mxs[x],tot-sz[x]);
if(mxs[x]<mxs[rt]) rt=x;
}
void get(int x,int fa)
{
a[++cur]=dis[x];
for(int i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
dis[v]=dis[x]+e[i].v;get(v,x);
}
}
int getdis(int x,int v)
{
cur=0;dis[x]=v;get(x,x);
int l,r=cur,ans=0;
sort(a+1,a+cur+1);
for(l=1;l<r;l++)
{
while(a[l]+a[r]>k&&r>=l) r--;
if(l<r&&a[r]+a[l]<=k) ans+=r-l;
}
//printf("%d %d %d
",x,v,ans);
//for(int i=1;i<=cur;i++) printf("%d ",dis[i]);
return ans;
}
void solve(int x)
{
int i;
final+=getdis(x,0);vis[x]=1;
for(i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]) continue;
final-=getdis(v,e[i].v);
}
for(i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]) continue;
rt=0;tot=sz[v];dfs(v,v);solve(rt);
}
}
int main()
{
int n,i,x,y,v;
scanf("%d",&n);
for(i=1;i<n;i++) scanf("%d%d%d",&x,&y,&v),add(x,y,v);
scanf("%d",&k);mxs[0]=n+1;dfs(1,1);solve(rt);
printf("%d
",final);
return 0;
}一些锅：mxs记得要每次重设为0然后sz记得要重算...细节挺多的考虑周全就好...（然而并不能）
二、类似树形DP的思想（？）
显然，我们的答案其实就是x的在两个不同的子树中取出两个点的答案。然后我们顺次枚举儿子，统计当前子树和之前访问的子树组合的答案即可。对于这个题，我们可以用桶维护个数，比如我们现在的dis为i然后我们可以让他和1~(k-dis)组合得到答案。于是我们需要求前缀和，这样时间复杂度是nklgn(大概是吧)，接受不了。我们可以用树状数组维护，因为树状数组常数非常小，是可以跑的，时间复杂度应该是nlgnlgk（吧）。emm等等我好像赋零就是nk咳咳咳，当他没有好了emm（其实是可以存下来一个个清的QwQ）
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 40010
#define lowbit(x) (x&-x)
using namespace std;
struct edge{int to,lt,v;}e[maxn<<1];
int in[maxn],cnt;bool vis[maxn];
int dis[maxn],sz[maxn],mxs[maxn];
int rt,tot,a[maxn],k,final,cur;
int tr[262145],azy[262145];
void modify(int x,int val)
{
while(x<=k)
{
tr[x]+=val;
x+=lowbit(x);
}
}
int query(int x)
{
int ans=0;
while(x)
{
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int y,int v)
{
e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].v=v;in[x]=cnt;
e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].v=v;in[y]=cnt;
}
void dfs(int x,int fa)
{
sz[x]=1;mxs[x]=0;
for(int i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
dfs(v,x);sz[x]+=sz[v];mxs[x]=max(mxs[x],sz[v]);
}
mxs[x]=max(mxs[x],tot-sz[x]);
if(mxs[x]<mxs[rt]) rt=x;
}
void get(int x,int fa)
{
//printf("%d %d
",x,dis[x]);
if(dis[x]<=k) a[++cur]=dis[x];
else return;
for(int i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
dis[v]=dis[x]+e[i].v;get(v,x);
}
}
/**int getdis(int x,int v)
{
dis[x]=v;get(x,x);
int ans=0,r;
for(int i=1;i<=k;i++)
{
r=query(i);
ans+=r*(query(k-i)-1);
//printf("%d %d %d
",x,i,r);
modify(i,-r);
}
//printf("%d %d %d
",x,v,ans);
//for(int i=1;i<=cur;i++) printf("%d ",dis[i]);
return ans;
}*/
void solve(int x)
{
int i,j;
//final+=getdis(x,1);
vis[x]=1;
for(i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]) continue;
cur=0;dis[v]=e[i].v;get(v,v);
for(j=1;j<=cur;j++) final+=query(k-a[j]);
for(j=1;j<=cur;j++) final++,modify(a[j],1);
}
for(i=1;i<=k;i++) tr[i]=0;
for(i=in[x];i;i=e[i].lt)
{
int v=e[i].to;
if(vis[v]) continue;
rt=0;tot=sz[v];dfs(v,v);solve(rt);
}
}
int main()
{
int n,i,x,y,v;
scanf("%d",&n);
for(i=1;i<n;i++) scanf("%d%d%d",&x,&y,&v),add(x,y,v);
scanf("%d",&k);mxs[0]=n+1;dfs(1,1);solve(rt);
printf("%d
",final);
return 0;
}点分治细节比较多，但其实好像比较套路。考场上一定要对拍因为这玩意细节太多，过了样例基本等于没过QAQ