题目大意:
给定n个点的无根树,树上每个点都有一个非负的点权.
树上的路径的价值定义为树上路径的点权和-树上路径的点权最大值;
现在给定一个参数P询问有多少条路径的价值是P的倍数(注意单点也算路径,路径不重复算)
这个题一眼就知道是点分治之类的鬼东西,第一眼觉得长得想聪聪可可,然后直接开了一个桶码起点分治,
但是有一个尴尬的地方就是在处理经过一个点的路径的时候我发现我不知道该怎么O(size)的转移,因为路径
上的最大值是不知道的,所以我考场上只打一个O(size^2)的转移(暴力枚举组合...),于是复杂度变成了n^2*logn
还不如n^2暴力...于是实力滚粗
好吧,我们想一想我们处理这个问题的瓶颈就是如何处理经过一个点的路径
我们又发现这个问题的瓶颈是处理这个max,由于不知道max所以我们只能暴力枚举组合
于是冥冥中我就蠢了,听大佬讲题的第一句话就想把自己的脸打肿
我们考虑让max变的有序起来
比如说我们把一这个点为根能遍历到的点按照max从小到达sort再依次加入与已有的边进行组合
这样有什么好处呢???
我们发现这样你每把当前这条边加入和原来的边进行组合的时候,由于已经按max排过序了,
他和别的边组合的max,就是他自己的max,这样组合的max的边就已知了,
这样你就可以直接查询桶了,然后加完后再把他自己的权值和放入桶中,和聪聪可可有点像
复杂度n*logn^2;
这题嘴巴AC很容易,但是由于他记的是点权,所以在处理的时候需要一些不同于边权的操作,所以在
摸爬滚打很久之后才AC
附上代码:
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#define lson num<<1
#define rson num<<1|1
#define int long long
using namespace std;
typedef long long ll;
const int N=300050;
const int Inf=2147483647;
int gi()
{
int x=0,flag=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*flag;
}
int head[N],nxt[N],to[N],P,n,ans;
int size[N],f[N],dis[N],maxn[N],vis[N];
int root,SIZE,v[N],tot,cnt,tong[10000050],used[N];
struct data{
int dis,maxn,id;
}w[N];
bool cmp(const data & a,const data &b){
return a.maxn<b.maxn;
}
void getroot(int x,int fa){
size[x]=1;f[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=fa&&!vis[y]){
getroot(y,x);
size[x]+=size[y];
f[x]=max(f[x],size[y]);
}
}
f[x]=max(f[x],SIZE-size[x]);
if(f[x]<f[root]) root=x;
}
void getdeep(int x,int fa){
w[++tot]=(data){dis[x],maxn[x],x};
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=fa&&!vis[y]){
dis[y]=(dis[x]+v[y])%P;
maxn[y]=max(maxn[x],v[y]);
getdeep(y,x);
}
}
}
int cal(int x,int y){
int ret=0,sum=0,tt=0;
tot=0;dis[x]=(v[x]+y)%P,maxn[x]=max(v[x],y);
getdeep(x,0);sort(w+1,w+1+tot,cmp);
//if(y) cout<<"是要减去的"<<' ';
//cout<<x<<"的子树中:"<<endl;
if(y==0) y=v[x];
for(int i=1;i<=tot;i++){
//cout<<w[i].dis<<' '<<w[i].maxn<<' '<<w[i].id<<"need:";
int now=(P+w[i].maxn+y-w[i].dis)%P;
//cout<<now<<' '<<tong[now]<<endl;
ret+=tong[now];
tong[w[i].dis]++;
used[++sum]=w[i].dis;
}
//cout<<"产生"<<ret<<"的贡献"<<endl;
//cout<<"---------"<<endl;
for(int i=1;i<=sum;i++) tong[used[i]]--;
return ret;
}
void work(int x){
ans+=cal(x,0);vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!vis[y]){
ans-=cal(y,v[x]);
SIZE=size[y];root=0;
getroot(y,root);work(root);
}
}
}
void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}
main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
n=gi(),P=gi();
for(int i=1;i<n;i++){
int x=gi(),y=gi();lnk(x,y);
}
for(int i=1;i<=n;i++) v[i]=gi();
root=0;f[0]=Inf;SIZE=n;getroot(1,0);work(root);ans+=n;
printf("%lld
",ans);
}