【日常小测】C

  • 本文为博主原创，未经许可不得转载

点分治，统计子树答案时记录路径上的最大点权，然后从小到大更新答案即可。

这样做保证了路径上的最大点权在当前的路径上。

注意：最后要把单点的情况加上。

PS：在测试时，我没能想到用这样的方法保证路径的合法性，也算是收获了一些人生的经验吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "read"
#define MAXN (int)(1e5+10)
#define INF (int)1e9
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct node{int y,next;}e[MAXN<<1];
int n,m,P,sum,root,len,tail,ans,Link[MAXN],cnt[10000010],v[MAXN],vsum[MAXN],vmax[MAXN],q[MAXN],size[MAXN],vis[MAXN],f[MAXN];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getc();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
	return x*f;
}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
bool cmp(int x,int y){return vmax[x]<vmax[y];}
void getroot(int x,int fa){
	size[x]=1;  f[x]=0;
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa&&!vis[e[i].y]){
		getroot(e[i].y,x);  size[x]+=size[e[i].y];
		if(size[e[i].y]>f[x]) f[x]=size[e[i].y];
	}
	if(sum-size[x]>f[x])  f[x]=sum-size[x];
	if(f[x]<f[root])  root=x;
}
void getv(int x,int fa){
	vsum[x]=(vsum[fa]+v[x])%P;vmax[x]=max(vmax[fa],v[x]);q[++tail]=x;
	for(int i=Link[x];i;i=e[i].next)
		if(e[i].y!=fa&&!vis[e[i].y])  getv(e[i].y,x);
}
int get(int x,int val,int fv){
	vsum[0]=vmax[0]=val;  tail=0;  getv(x,0);
	sort(q+1,q+tail+1,cmp); int ret=0;
	for(int i=1;i<=tail;++i){
		int now=q[i];  if(vsum[now]<0)  vsum[now]+=P;
		int temp=(vmax[now]-vsum[now]+fv)%P;
		if(temp<0)  temp+=P;
		ret+=cnt[temp];  cnt[vsum[now]]++;
	}
	for(int i=1;i<=tail;++i)  cnt[vsum[q[i]]]=0;
	return ret;
}
void solve(int x){
	ans+=get(x,0,v[x]);  vis[x]=1;
	for(int i=Link[x];i;i=e[i].next)if(!vis[e[i].y]){
		ans-=get(e[i].y,v[x],v[x]);
		sum=size[e[i].y];  root=0;
		getroot(e[i].y,0); solve(root);
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=sum=read();  P=read();  f[0]=INF;
	for(int i=1;i<n;++i) {int x=read(),y=read(); insert(x,y); insert(y,x);}
	for(int i=1;i<=n;++i)  v[i]=read();
	getroot(1,0);  solve(root);
	printf("%d\n",ans+n);
	return 0;
}

本文标题:【日常小测】C

文章作者:chty

发布时间:2017年03月24日 - 19时07分

最后更新:2018年07月25日 - 21时31分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,