点分治模板题
关键: 找重心 –> 对路径的处理 –>通过容斥或者树状数组方式解决当前经过重心情况并划归子问题处理
一定要对每次处理保证O(tot)的时间复杂度
#include<bits/stdc++.h>
using namespace std;
int N,K;
const int MAXN = 1e4 + 10;
struct edge{
int v,w;
edge(int v=0,int w=0):v(v),w(w){}
};
vector<edge>adj[MAXN];
int rt,cnt = 0;
int d[MAXN];
int sz[MAXN];
bool vis[MAXN];
void dfs_rt(int u,int fa,int tot){
sz[u] = 1;
int n = 0,v;
for(int k=0;k<adj[u].size();k++){
v = adj[u][k].v;
if(v == fa || vis[v]) continue;
dfs_rt(v,u,tot);
sz[u] += sz[v];
n = max(n,sz[v]);
}
n = max(n,tot - sz[u]);
if(n * 2 <= tot) rt = u;
}
void dfs_dis(int u,int fa,int dis){
d[++cnt] = dis;
int v,w;
for(int k=0;k<adj[u].size();k++){
v = adj[u][k].v;
w = adj[u][k].w;
if(v == fa || vis[v]) continue;
dfs_dis(v,u,dis + w);
}
}
int calc(int u,int w){
cnt = 0;
dfs_dis(u,0,w);
sort(d+1,d+1+cnt);
int l = 1,r = cnt,ans = 0;
//双指针求出所有合法情况
while(l < r){
while(d[l] + d[r] > K && l < r) --r;
ans += r - l;
l++;
}
return ans;
}
int work(int u,int tot){
dfs_rt(u,0,tot);//找重心
u = rt;
dfs_rt(u,0,tot);//对重心为根的树重找一遍sz
vis[u] = 1;//标记已分治
int v,w;
int ans = calc(u,0);//当前经过所有重心的所有情况
for(int k=0;k<adj[u].size();k++){
v = adj[u][k].v;
w = adj[u][k].w;
if(vis[v]) continue;
ans -= calc(v,w);//容斥减去非法情况(即两个点均在一颗子树里)
ans += work(v,sz[v]);//递归子情况
}
return ans;
}
int main(){
while(cin >> N >> K){
if(!N && !K) break;
for(int i=1;i<=N;i++) adj[i].clear();
for(int i=1;i<=N;i++) vis[i] = 0;
for(int i=1;i<=N-1;i++){
int a,b,w;
cin >> a >> b >> w;
++a;
++b;
adj[a].push_back(edge(b,w));
adj[b].push_back(edge(a,w));
}
cout << work(1,N) << endl;
}
return 0;
}