题目
Description
给一棵n个节点的无根树，每个节点有个非负整点权，定义一条路径的价值为路径上的(点权和)-(点权最大值)
给定参数p，求有多少条不同的简单路径满足它的价值恰好为p的倍数。
注意，单点也算做一个路径，u!=v时,u->v和v->u算作一条路径。
简单路径就是不经过重复点的一条路径。
[nleqslant 10^5 \
pleqslant 10^7 \
v[i] leqslant 10^9
]
Input
第一行包含两个数 n,p;
接下来n-1行，每行两个数表示那两个点之间有一条树边;
接下来一行n个整数 (v[1]~v[n])，表示点 i 的权值.
Outpug
就一个数，表示答案
Sample Input
5 2
1 2
1 3
2 4
3 5
1 3 3 1 2
Sample Output
9
Hint
满足条件的路径有:
(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(2,3),(2,5),(3,5)
分析
- 数据庞大，所以考虑点分治
- 基本过程和模板题差不多，不过关于减去最大点权这一点，我们应该稍作处理。
- 可以每次求 dis[] 时，把 mx[] 也顺便求出来（这条路径中最大点权），之后以 mx[] 排个序，之后就能 O(n) 处理出当前子树的答案了。（具体可以看一看程序中的一小段注释）
- 注意，求 dis[] 的时候就应该先
%p。 - 还有一点，单点也算是一条路径，而显然单点路径的价值为0，那么肯定是可以有贡献的，于是最后输出
ans+n。
程序
#include <cstdio>
#include <algorithm>
#define Mn 100005
#define Mv 10000005
#define add(x,y) (to[++num]=head[x],head[x]=num,edge[num]=y)
#define For(x) for (int h=head[x],o=edge[h]; h; o=edge[h=to[h]])
using namespace std;
int n,p,ans;
int edge[2*Mn+5],to[2*Mn+5],head[2*Mn+5],del[Mn+5],num;
int R,cnt,mins,v[Mn+5],dis[Mn+5],siz[Mn+5],mx[Mn+5],com[Mn+5],bin[Mv+5],daan;
/*部分变量说明
del[i] 节点 i 还在不在(每次分治完都把重心去掉了，免得又dfs回到上面)
dis[] 从重心到子树中各个节点的路径价值的集合
mx[] dis[]中各个路径对应的最大点权值
bin[i] 一个容器，存储到当前 dis[] 为 i 的路径个数(具体用法可以看看程序)
com[] 辅助排序(看看cmp应该就能懂了)
siz[i] 当前重心下以 x 为根节点的子树的大小
*/
int mo(int x){
int kkk=x%p;
return (kkk<0 ? kkk+p:kkk);
}
void Input(){
scanf("%d%d",&n,&p);
for (int i=1,o1,o2; i<n; i++) scanf("%d%d",&o1,&o2),add(o1,o2),add(o2,o1);
for (int i=0; i<n;) scanf("%d",&v[++i]);
return;
}
int get_siz(int x,int fa){
siz[x]=1;
For (x) if (o!=fa && !del[o]) siz[x]+=get_siz(o,x);
return siz[x];
}
void dfs_R(int x,int tot,int fa){ //求重心(比较 x 变为中心的话分出的子树中大小最大值)
int mxs=tot-siz[x];
For(x) if (o!=fa && !del[o]){
mxs=max(mxs,siz[o]);
dfs_R(o,tot,x);
}
if (mxs<mins) mins=mxs,R=x;
}
void get_dis(int x,int tot,int lmx,int fa){ //求子树中每个点到重心这条路径的价值
dis[++cnt]=tot%=p;//-----------------!!!!!就是这里我忘记 %，调了一中午 T^T
mx[cnt]=lmx;
For(x) if (!del[o] && o!=fa)
get_dis(o,tot+v[o],max(lmx,v[o]),x);
}
bool cmp(int x,int y){return mx[x]<mx[y];}
int work(int x,int r){
//处理当前中心下两端点都在以 x 为根节点的子树中经过重心的符合路径个数(先不管是不是"简单路径")
cnt=daan=0;
if (x==r) get_dis(x,v[x],v[x],0);
else get_dis(x,v[x]+v[r],max(v[x],v[r]),r);
for (int i=1; i<=cnt; i++) com[i]=i;
sort(com+1,com+cnt+1,cmp);
for (int i=1,I=com[i]; i<=cnt; I=com[++i]){
//dis[I]+dis[j]-v[r]-mx[I] == 0 (%p)
//dis[j] == v[r]+mx[I]-dis[I] (%p)
//大概意思就是一个端点为 I ,另一个端点为 mx[] 小于等于 mx[I](即已经加入bin[]中的端点)
daan+=bin[mo(mx[I]+v[r]-dis[I])];
bin[dis[I]]++;
}
for (int i=1; i<=cnt; i++) bin[dis[i]]=0;
return daan;
}
void dfs(int x){ //分治总过程
cnt=0;
mins=Mn+1;
get_siz(x,0);
dfs_R(x,siz[x],0);
int rr=R;
ans+=work(rr,rr);
del[rr]=1;
For(rr) if (!del[o]){
ans-=work(o,rr);
dfs(o);
}
}
int main(){
Input();
dfs(1);
printf("%lld",ans+n);
}
提示
- 这是我做的第二道点分题，还是有点不熟练，起先一直 RE，调了一中午才发现原来是在 get_dis() 那里我的 tot 并没有
%，于是数据一大，tot 就会溢出int，导致答案错误了。 - 可以先看看我打的第一道点分治题（模板题）: 传送门
- 大家加油呀~