这是一个淀粉质的板子题
先来讲一讲淀粉质(就以这个题当例子)
题面要求我们统计长度小于等于K的路径数
假如我们以$u$为根
那么满足条件的路径就可以分为两种:
1.经过u
2.不经过u
对于经过u的部分,我们直接统计(先别管统计方式)
而不经过u的部分,显然就是在删去u之后,形成的各个连通块的相同子问题
于是分治的思路就出来了
别慌,考虑这样一个问题:
这个是树欸,可不是线性的数组
数组可以直接从中点分,$O(n\log(n))$肯定稳的
然而树这玩意儿......
有个东西叫做树的重心(其实就是一个点)
对于树上的每一个点,删去后都会形成若干连通块
对于某个点,若删去它后形成的最大的连通块的大小最小,我们称该点为树的重心
口胡的,没看懂请去百度
显然,若每次以当前连通块(树)的重心来分治,就可以做到$O(n\log(n))$
树的重心的求法如下
void Find(int u,int p,int tot) {//tot是当前连通块的总大小
size[u]=1;
mx[u]=0;
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i];
if(vis[v]||v==p)
continue;
Find(v,u,tot);
size[u]+=size[v];
mx[u]=max(mx[u],size[v]);
}
mx[u]=max(mx[u],tot-size[u]);//非子树部分崩出的连通块也要算上
if(mx[u]<mx[root])
root=u;
}
有一点树形dp基础的应该都毫无压力吧
每次求出树的重心之后都要再以树的重心为根算一遍size,不然size是错的(想一想为什么)
接着就可以分治了
void Divide(int u) {
vis[u]=1;
Getans(u);
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i];
if(vis[v])
continue;
mx[root=0]=INF;
Find(v,u,size[v]);
Calc(root,0);//这其实就是Find,只是我有强迫症,非要再打一个
Divide(root);
}
}
考虑如何设计$Getans(u)$
我们求出u的第i棵子树中所有链的长度
那么有两种组合方式可能对答案产生贡献:
1.这条链本身就比K短
2.和前i-1棵子树中某条链拼接(当然长度不能大于K)
第一种直接暴力就好
第二种开个树状数组枚举大力统计就行了
然后,你就发现,T飞了(5个点)
你百思不得其解,开始debug
然后,“为什么会有零边啊!!!那树状数组不就卡死了吗!!!”
自闭了?
没事,自闭完了接着看
我们考虑加一个偏移量,把零边变成非零边
就可以切了它了
void Getdis(int u,int p) {
rem[++cnt]=dis[u];//暂时不能统计进去,避免同一子树内的链拼接在一起
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i],w=W[u][i];
if(vis[v]||v==p)
continue;
dis[v]=dis[u]+w;
Getdis(v,u);
}
}
void Getans(int u) {
dis[u]=0;
int q=0;
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i],w=W[u][i];
if(vis[v])
continue;
cnt=0;
dis[v]=dis[u]+w;
Getdis(v,u);
for(int i=1; i<=cnt; i++) {
++rem[i];//偏移量
int nxt=K+2-rem[i];//因为每条链的长度都+1,所以K的放宽到K+2
ans+=Sum(nxt)+(rem[i]<=K+1);//0还得算上,K+1不解释
}
for(int i=1; i<=cnt; i++) {
P[++q]=rem[i];
Add(rem[i],1);//这个时候再把当前子树所有链怼到树状数组里去
}
}
for(int i=1; i<=q; i++)
Add(P[i],-1);//清空树状数组
}
完整代码如下:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int INF=0x3f3f3f3f;
const int maxm=1e7;
int N,K,root,mx[maxn],vis[maxn],size[maxn],dis[maxn];
int rem[maxn],cnt,C[maxm+5],P[maxn],ans;
vector<int>G[maxn],W[maxn];
int lowbit(int x) {
return x&(-x);
}
void Add(int x,int k) {
while(x<=maxm) {
C[x]+=k;
x+=lowbit(x);
}
}
int Sum(int x) {
int ans=0;
while(x>0) {
ans+=C[x];
x-=lowbit(x);
}
return ans;
}
void Find(int u,int p,int tot) {
size[u]=1;
mx[u]=0;
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i];
if(vis[v]||v==p)
continue;
Find(v,u,tot);
size[u]+=size[v];
mx[u]=max(mx[u],size[v]);
}
mx[u]=max(mx[u],tot-size[u]);
if(mx[u]<mx[root])
root=u;
}
void Calc(int u,int p) {
size[u]=1;
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i];
if(vis[v]||v==p)
continue;
Calc(v,u);
size[u]+=size[v];
}
}
void Getdis(int u,int p) {
rem[++cnt]=dis[u];
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i],w=W[u][i];
if(vis[v]||v==p)
continue;
dis[v]=dis[u]+w;
Getdis(v,u);
}
}
void Getans(int u) {
dis[u]=0;
int q=0;
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i],w=W[u][i];
if(vis[v])
continue;
cnt=0;
dis[v]=dis[u]+w;
Getdis(v,u);
for(int i=1; i<=cnt; i++) {
++rem[i];
int nxt=K+2-rem[i];
ans+=Sum(nxt)+(rem[i]<=K+1);
}
for(int i=1; i<=cnt; i++) {
P[++q]=rem[i];
Add(rem[i],1);
}
}
for(int i=1; i<=q; i++)
Add(P[i],-1);
}
void Divide(int u) {
vis[u]=1;
Getans(u);
for(int i=0; i<G[u].size(); i++) {
int v=G[u][i];
if(vis[v])
continue;
mx[root=0]=INF;
Find(v,u,size[v]);
Calc(root,0);
Divide(root);
}
}
void Init(){
for(int i=1;i<=N;i++){
G[i].clear();
W[i].clear();
}
memset(vis,0,sizeof(vis));
ans=0;
}
int main() {
freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
while(cin>>N>>K&&N&&K) {
Init();
for(int i=1,u,v,w; i<N; i++) {
cin>>u>>v>>w;
u++,v++;
G[u].push_back(v);
G[v].push_back(u);
W[u].push_back(w);
W[v].push_back(w);
}
mx[root=0]=INF;
Find(1,0,N);
Calc(root,0);
Divide(root);
cout<<ans<<endl;
}
return 0;
}//by uniecho1
《淀粉质》
Divide里的Calc(v,u);写错了吧,应该是Calc(root,0);才对,因为每次求出树的重心之后都要再以树的重心为根算一遍size,虽然这样也过了,但应该是数据问题吧
emmm确实是我的问题…已修正,感谢提醒
这个完整代码好像过不了