我当时模数写错了也是只对了最后一个点,您可以试试把所有跟答案有关的地方都开long long
by lmxcslD @ 2021-01-13 23:38:53
(包括传参的时候
by lmxcslD @ 2021-01-13 23:42:09
@[fhqTreap](/user/358957) 现在 55pts 了 qwq
我再看看
by tiger2005 @ 2021-01-13 23:44:29
@[fhqTreap](/user/358957) 目前是 55pts
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
// Splay
const long long MAXN = 2e5 + 10;
const long long Md = 51061;
long long cc[MAXN][2],fa[MAXN];
bool rev[MAXN];
long long val[MAXN],adt[MAXN],ans[MAXN],mul[MAXN],siz[MAXN];
inline void pushUp(long long x){
if(x==0) return;
ans[x]=(ans[cc[x][0]]+ans[cc[x][1]]+val[x])%Md;
siz[x]=siz[cc[x][0]]+siz[cc[x][1]]+1;
}
inline void revSplay(long long x){
swap(cc[x][0],cc[x][1]),rev[x]^=1;
}
inline void addSplay(long long x,long long v){
(adt[x]+=v)%=Md;(ans[x]+=v*siz[x])%=Md;(val[x]+=v)%=Md;
}
inline void mulSplay(long long x,long long v){
(adt[x]*=v)%=Md;(mul[x]*=v)%=Md;(val[x]*=v)%=Md;(ans[x]*=v)%=Md;
}
inline void pushDown(long long x){
if(mul[x]!=1){
if(cc[x][0]) mulSplay(cc[x][0],mul[x]);
if(cc[x][1]) mulSplay(cc[x][1],mul[x]);
mul[x]=1;
}
if(adt[x]){
if(cc[x][0]) addSplay(cc[x][0],adt[x]);
if(cc[x][1]) addSplay(cc[x][1],adt[x]);
adt[x]=0;
}
if(rev[x]){
if(cc[x][0]) revSplay(cc[x][0]);
if(cc[x][1]) revSplay(cc[x][1]);
rev[x]=false;
}
}
// Start - nroot
inline bool nroot(long long x){
return cc[fa[x]][0]==x || cc[fa[x]][1]==x;
}
// End - nroot
inline void rtt(long long x){
long long y=fa[x],z=fa[y],k=(cc[y][1]==x);
if(z && nroot(y))
cc[z][cc[z][1]==y]=x;
fa[x]=z;
cc[y][k]=cc[x][!k];
if(cc[x][!k]) fa[cc[x][!k]]=y;
cc[x][!k]=y;fa[y]=x;
pushUp(y);pushUp(x);
}
vector<long long> stk;
inline void splay(long long x,long long g=0){
long long q=x;stk.push_back(q);
while(nroot(q)) stk.push_back(q=fa[q]);
while(!stk.empty()) pushDown(stk.back()),stk.pop_back();
while(nroot(x)){
long long y=fa[x],z=fa[y];
if(nroot(y))
((cc[z][0]==y)^(cc[y][0]==x))?rtt(x):rtt(y);
rtt(x);
}
pushUp(x);
}
// Link Cut Tree
inline void access(long long x){
for(long long y=0;x;x=fa[y=x])
splay(x),cc[x][1]=y,pushUp(x);
}
inline void makeRoot(long long x){
access(x);splay(x);revSplay(x);
}
inline long long findRoot(long long x){
access(x);splay(x);
while(cc[x][0]) pushDown(x),x=cc[x][0];
splay(x);return x;
}
inline void split(long long x,long long y){
makeRoot(x);access(y);splay(y);
}
//inline void link(long long x,long long y){
// makeRoot(x);
// if(findRoot(y)==x) return;
// fa[x]=y;pushUp(y);
//}
//inline void cut(long long x,long long y){
// makeRoot(x);
// if(findRoot(y)!=x || fa[y]!=x || cc[y][0]) return;
// fa[y]=cc[x][1]=0;pushUp(x);
//}
inline void link(long long x,long long y){
makeRoot(x);fa[x]=y;pushUp(y);
}
inline void cut(long long x,long long y){
split(x,y);fa[x]=cc[y][0]=0;
}
long long N,M;
int main(){
scanf("%lld%lld",&N,&M);
for(long long i=1;i<=N;i++) mul[i]=siz[i]=val[i]=ans[i]=1;
for(long long i=1,x,y;i<N;i++){
scanf("%lld%lld",&x,&y);link(x,y);
}
long long x,y;
long long z;
char typ[2];
while(M--){
scanf(" %s",typ);
if(typ[0]=='+'){
scanf("%lld%lld%lld",&x,&y,&z);
split(x,y);addSplay(y,z);
}
else if(typ[0]=='-'){
scanf("%lld%lld",&x,&y);cut(x,y);
scanf("%lld%lld",&x,&y);link(x,y);
}
else if(typ[0]=='*'){
scanf("%lld%lld%lld",&x,&y,&z);
split(x,y);mulSplay(y,z);
}
else if(typ[0]=='/'){
scanf("%lld%lld",&x,&y);
split(x,y);printf("%lld\n",ans[y]);
}
}
return 0;
}
```
by tiger2005 @ 2021-01-13 23:50:48
@[fhqTreap](/user/358957) AC 了,十分感谢。
Code:
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
// Splay
const long long MAXN = 2e5 + 10;
const long long Md = 51061;
long long cc[MAXN][2],fa[MAXN];
bool rev[MAXN];
long long val[MAXN],adt[MAXN],ans[MAXN],mul[MAXN],siz[MAXN];
inline void pushUp(long long x){
if(x==0) return;
ans[x]=(ans[cc[x][0]]+ans[cc[x][1]]+val[x])%Md;
siz[x]=siz[cc[x][0]]+siz[cc[x][1]]+1;
}
inline void revSplay(long long x){
swap(cc[x][0],cc[x][1]),rev[x]^=1;
}
inline void addSplay(long long x,long long v){
(adt[x]+=v)%=Md;(ans[x]+=v*siz[x])%=Md;(val[x]+=v)%=Md;
}
inline void mulSplay(long long x,long long v){
(adt[x]*=v)%=Md;(mul[x]*=v)%=Md;(val[x]*=v)%=Md;(ans[x]*=v)%=Md;
}
inline void pushDown(long long x){
if(mul[x]!=1){
if(cc[x][0]) mulSplay(cc[x][0],mul[x]);
if(cc[x][1]) mulSplay(cc[x][1],mul[x]);
mul[x]=1;
}
if(adt[x]){
if(cc[x][0]) addSplay(cc[x][0],adt[x]);
if(cc[x][1]) addSplay(cc[x][1],adt[x]);
adt[x]=0;
}
if(rev[x]){
if(cc[x][0]) revSplay(cc[x][0]);
if(cc[x][1]) revSplay(cc[x][1]);
rev[x]=false;
}
}
// Start - nroot
inline bool nroot(long long x){
return cc[fa[x]][0]==x || cc[fa[x]][1]==x;
}
// End - nroot
inline void rtt(long long x){
long long y=fa[x],z=fa[y],k=(cc[y][1]==x);
if(z && nroot(y))
cc[z][cc[z][1]==y]=x;
fa[x]=z;
cc[y][k]=cc[x][!k];
if(cc[x][!k]) fa[cc[x][!k]]=y;
cc[x][!k]=y;fa[y]=x;
pushUp(y);pushUp(x);
}
vector<long long> stk;
inline void splay(long long x){
long long q=x;stk.push_back(q);
while(nroot(q)) stk.push_back(q=fa[q]);
while(!stk.empty()) pushDown(stk.back()),stk.pop_back();
while(nroot(x)){
long long y=fa[x],z=fa[y];
if(nroot(y))
((cc[z][0]==y)^(cc[y][0]==x))?rtt(x):rtt(y);
rtt(x);
}
pushUp(x);
}
// Link Cut Tree
inline void access(long long x){
for(long long y=0;x;x=fa[y=x])
splay(x),cc[x][1]=y,pushUp(x);
}
inline void makeRoot(long long x){
access(x);splay(x);revSplay(x);
}
inline long long findRoot(long long x){
access(x);splay(x);
while(cc[x][0]) pushDown(x),x=cc[x][0];
return x;
}
inline void split(long long x,long long y){
makeRoot(x);access(y);splay(y);
}
inline void link(long long x,long long y){
makeRoot(x);
if(findRoot(x)!=y) fa[x]=y;
}
inline void cut(long long x,long long y){
makeRoot(x);split(x,y);
if(findRoot(y)==x && fa[x]==y && !cc[x][1])
fa[x]=cc[y][0]=0;
}
long long N,M;
int main(){
scanf("%lld%lld",&N,&M);
for(long long i=1;i<=N;i++) mul[i]=siz[i]=val[i]=1;
for(long long i=1,x,y;i<N;i++){
scanf("%lld%lld",&x,&y);link(x,y);
}
long long x,y,z;
char typ[2];
while(M--){
scanf(" %s",typ);
if(typ[0]=='+'){
scanf("%lld%lld%lld",&x,&y,&z);
split(x,y);addSplay(y,z);
}
else if(typ[0]=='-'){
scanf("%lld%lld",&x,&y);cut(x,y);
scanf("%lld%lld",&x,&y);link(x,y);
}
else if(typ[0]=='*'){
scanf("%lld%lld%lld",&x,&y,&z);
split(x,y);mulSplay(y,z);
}
else if(typ[0]=='/'){
scanf("%lld%lld",&x,&y);
split(x,y);printf("%lld\n",ans[y]);
}
}
return 0;
}
```
by tiger2005 @ 2021-01-14 00:04:07
51061*51061>2147483647
by MatrixCascade @ 2021-01-14 07:15:49
您怎么两天一个算法(雾
by oisdoaiu @ 2021-01-14 08:05:44
@[MatrixCascade](/user/154101) 实际上是重写了一次 link 和 cut
by tiger2005 @ 2021-01-14 08:54:04
@[tiger2005](/user/60864) dbq,我以前自己写和帮别人调的时候都是没开 ll 5 分,所以就直接说了
by MatrixCascade @ 2021-01-14 08:56:39
@[MatrixCascade](/user/154101) 我在开完 ll 之后是 55 pts .jpg
by tiger2005 @ 2021-01-14 09:21:28