题目描述
给定一棵树，点有点权，有三种操作：路径上的点点权加上v，路径上的点点权改成v，查询一条路径和并判断这个和是否能够分成两个质数。
对于100%的数据，1≤n,m≤100000，1≤x,y≤n，一直满足0≤Ai,S≤10000000。在增加事件中v可能为负数。 S:路径和
题解
看见题还是可以看得出是裸的树链剖分；对于两个质数分解也可以想得到哥德巴赫猜想，对于>=4的偶数都可以分成两个质数，奇数如果要分成两个质数就只可能是2+一个质数，观察到路径和是1e7,所以存下3500的以内的质数判断即可，或者直接预处理出1e7的bool数组，对于0,1,2这些小的数注意一下就好。
比较有趣的是标记的下放，其实慢慢思考也可以想到，覆盖标记会直接修改值，不管前面的+标记；所以下放顺序应该是先下放覆盖标记，再下放+标记，在下放覆盖标记时还要清空节点的+标记。
这些多想想一个可以明白，代码还是比较清晰。
#include<bits/stdc++.h> using namespace std; const int maxn=100005; const int maxx=3500; int n,m; int a[maxn],aa[maxn]; int dep[maxn],size[maxn],fa[maxn],son[maxn]; int num,top[maxn],id[maxn]; int root,ls[maxn<<1],rs[maxn<<1],len[maxn<<1]; int sum[maxn<<1],tag[maxn<<1],cover[maxn<<1]; int cnt,prime[maxn]; bool not_prime[maxn]; vector<int>e[maxn]; template<class T>inline void read(T &x){ x=0;int f=0;char ch=getchar(); while(!isdigit(ch)) {f|=(ch=='-');ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x= f ? -x : x ; } void init(){ not_prime[1]=true; for(int i=2;i<=maxx;i++){ if(!not_prime[i]) prime[++cnt]=i; for(int j=1;j<=cnt;j++){ if(prime[j]*i>maxx) break; not_prime[i*prime[j]]=true; if(i%prime[j]==0) break; } } } void dfs(int u){ size[u]=1; for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==fa[u]) continue; fa[v]=u; dep[v]=dep[u]+1; dfs(v); size[u]+=size[v]; if(size[son[u]]<size[v]) son[u]=v; } } void dfs(int u,int tp){ id[u]=++num; aa[num]=a[u]; top[u]=tp; if(!son[u]) return ; dfs(son[u],tp); for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==fa[u]||v==son[u]) continue; dfs(v,v); } } void update(int rt){ sum[rt]=sum[ls[rt]]+sum[rs[rt]]; } void build(int &rt,int l,int r){ rt=++num; len[rt]=r-l+1; cover[rt]=-1; if(l==r){ sum[rt]=aa[l]; return ; } int mid=(l+r)>>1; build(ls[rt],l,mid); build(rs[rt],mid+1,r); update(rt); } void put_tag(int rt,int val){ tag[rt]+=val; sum[rt]+=val*len[rt]; } void put_cover(int rt,int val){ tag[rt]=0; cover[rt]=val; sum[rt]=val*len[rt]; } void push_down(int rt){ if(cover[rt]!=-1){ put_cover(ls[rt],cover[rt]); put_cover(rs[rt],cover[rt]); cover[rt]=-1; } if(tag[rt]){ put_tag(ls[rt],tag[rt]); put_tag(rs[rt],tag[rt]); tag[rt]=0; } } void modifytag(int rt,int l,int r,int a_l,int a_r,int val){ if(a_l<=l&&r<=a_r){ put_tag(rt,val); return ; } push_down(rt); int mid=(l+r)>>1; if(a_l<=mid) modifytag(ls[rt],l,mid,a_l,a_r,val); if(mid<a_r) modifytag(rs[rt],mid+1,r,a_l,a_r,val); update(rt); } void modifytag(int x,int y,int val){ while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]) swap(x,y); modifytag(1,1,n,id[top[y]],id[y],val); y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); modifytag(1,1,n,id[x],id[y],val); } void modifycover(int rt,int l,int r,int a_l,int a_r,int val){ if(a_l<=l&&r<=a_r){ put_cover(rt,val); return ; } push_down(rt); int mid=(l+r)>>1; if(a_l<=mid) modifycover(ls[rt],l,mid,a_l,a_r,val); if(mid<a_r) modifycover(rs[rt],mid+1,r,a_l,a_r,val); update(rt); } void modifycover(int x,int y,int val){ while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]) swap(x,y); modifycover(1,1,n,id[top[y]],id[y],val); y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); modifycover(1,1,n,id[x],id[y],val); } int query(int rt,int l,int r,int a_l,int a_r){ if(a_l<=l&&r<=a_r) return sum[rt]; push_down(rt); int mid=(l+r)>>1; int ret=0; if(a_l<=mid) ret+=query(ls[rt],l,mid,a_l,a_r); if(mid<a_r) ret+=query(rs[rt],mid+1,r,a_l,a_r); return ret; } bool get(int x){ if(x<=maxx) return !not_prime[x]; for(int i=1;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return false; return true; } bool check(int x){ if(x&1){//奇数 if(x==1) return false; if(get(x-2)) return true;//x=2+质数 return false; } //偶数 if(!x||x==2) return false; return true;//哥德巴赫猜想 } bool query(int x,int y){ int ret=0; while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]) swap(x,y); ret+=query(1,1,n,id[top[y]],id[y]); y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); ret+=query(1,1,n,id[x],id[y]); //printf("%d ",ret); return check(ret); } int main(){ freopen("japari.in","r",stdin); freopen("japari.out","w",stdout); init(); // printf("%d ",cnt); // for(int i=1;i<=cnt;i++) printf("%d ",prime[i]); read(n);read(m); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<n;i++){ int x,y; read(x);read(y); e[x].push_back(y); e[y].push_back(x); } dep[1]=1; dfs(1); dfs(1,1); num=0; build(root,1,n); for(int i=1;i<=m;i++){ int opt,x,y; read(opt);read(x);read(y); if(opt==1){ int v;read(v); modifytag(x,y,v); } else if(opt==2){ int v;read(v); modifycover(x,y,v); } else printf("%s ",query(x,y) ? "SUGOI" : "TANOSHI"); } } /* 3 4 1 2 1 2 1 3 2 2 2 1 4 1 3 3 -1 2 2 2 2 3 1 3 4 6 2 4 0 0 2 1 3 2 4 3 2 1 4 2 1 4 4 9 1 3 2 -2 2 4 2 5 3 1 4 3 4 4 */