样例没过。
看代码错误数量而定,找出一个错是 3关注,两个错是 5 关注+5RMB,三个错及以上就是 5关注&15 RMB,多个人关注按着最先的那个人的数量,最多 5 个,钱按着本应拿的钱为权值平分。
代码在下面。
#include<bits/stdc++.h>
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader(){}
} cin;
const char endl = '\n';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
const int N=500005,inf=0x3f3f3f3f,fni=0xc0c0c0c0;
int n,q,rt,st[N],top,cnt;
struct edge{int u,v;}e[N];
struct Lazy
{
int mul,add;
Lazy(){mul=1;add=0;}
Lazy(int mul,int add):mul(mul),add(add){}
bool isval(){return mul!=1||add!=0;}
Lazy operator+(Lazy x)const{return Lazy(mul*x.mul,add*x.mul+x.add);}
};
struct node
{
int sz,sum,mn,mx;
node(){sz=sum=0;mn=inf;mx=fni;}
node(int sz,int sum,int mn,int mx):sz(sz),sum(sum),mn(mn),mx(mx){}
node operator+(node x)const{return node(sz+x.sz,sum+x.sum,min(mn,x.mn),max(mx,x.mx));}
node operator+(Lazy x)const{return node(sz,sum*x.mul+sz*x.add,mn==inf?inf:mn*x.mul+x.add,mx==fni?fni:mx*x.mul+x.add);}
};
struct Node
{
int fa,ch[3],w,lazyr;
Lazy lazyp,lazys;
node sump,sums;
void init(){lazyp=lazys=Lazy();sump=sums=node();fa=ch[0]=ch[1]=ch[2]=w=lazyr=0;}
}satt[N];
int &ls(int u){return satt[u].ch[0];}
int &rs(int u){return satt[u].ch[1];}
int &ms(int u){return satt[u].ch[2];}
int &fa(int u){return satt[u].fa;}
int &ch(int u,int w){return satt[u].ch[w];}
int &w(int u){return satt[u].w;}
int &lazyr(int u){return satt[u].lazyr;}
Lazy &lazyp(int u){return satt[u].lazyp;}
Lazy &lazys(int u){return satt[u].lazys;}
node &sump(int u){return satt[u].sump;}
node &sums(int u){return satt[u].sums;}
void clear(int u){satt[u].init();st[++top]=u;}
int getid(){return top?st[top--]:cnt++;}
bool checklr(int u){return u==rs(fa(u));}
bool isroot(int u){return u!=ls(fa(u))&&u!=rs(fa(u));}
void Set(int u,int v,int w){if(u)fa(u)=v;ch(v,w)=u;}
void pushlazyr(int u){swap(ls(u),rs(u));lazyr(u)^=1;}
void pushlazyp(int u,Lazy l)
{
w(u)=w(u)*l.mul+l.add;
lazyp(u)=lazyp(u)+l;
sump(u)=sump(u)+l;
}
void pushlazys(int u,Lazy l)
{
lazys(u)=lazys(u)+l;
sums(u)=sums(u)+l;
}
void pushup(int u,int tp)
{
if(tp)sums(u)=sums(ls(u))+sums(rs(u))+sums(ms(u))+sump(ms(u));
else
{
sums(u)=sums(ls(u))+sums(rs(u))+sums(ms(u));
sump(u)=sump(ls(u))+node(1,w(u),w(u),w(u))+sump(rs(u));
}
}
void pushdown(int u,int tp)
{
if(tp){if(lazys(u).isval())
{
pushlazys(ls(u),lazys(u));
pushlazys(rs(u),lazys(u));
pushlazys(ms(u),lazys(u));
pushlazyp(ms(u),lazys(u));
lazys(u)=Lazy();
}}
else
{
if(lazyr(u))
{
pushlazyr(ls(u));
pushlazyr(rs(u));
lazyr(u)=0;
}
if(lazyp(u).isval())
{
pushlazyp(ls(u),lazyp(u));
pushlazyp(rs(u),lazyp(u));
lazyp(u)=Lazy();
}
if(lazys(u).isval())
{
pushlazys(ls(u),lazys(u));
pushlazys(rs(u),lazys(u));
pushlazys(ms(u),lazys(u));
lazys(u)=Lazy();
}
}
}
void pushall(int u,int tp){if(!isroot(u))pushall(fa(u),tp);pushdown(u,tp);}
void rotate(int u,int tp)
{
int f=fa(u),gf=fa(f),lr=checklr(u),son=ch(u,!lr);
if(gf)ch(gf,ms(gf)==f?2:checklr(f))=u;
if(son)fa(son)=f;
fa(u)=gf;ch(u,!lr)=f;
fa(f)=u;ch(f,lr)=son;
pushup(f,tp);pushup(u,tp);
}
void splay(int u,int tp,int v=0)
{
pushall(u,tp);
for(int f;f=fa(u),!isroot(u)&&f!=v;rotate(u,tp))if(fa(f)!=v&&!isroot(v))rotate(checklr(u)==checklr(f)?f:u,tp);
}
void del(int u)
{
Set(ms(u),fa(u),1);
if(ls(u))
{
int v=ls(u);
pushdown(v,1);
while(rs(v)){v=rs(v);pushdown(v,1);}
splay(v,1,u);
Set(rs(u),v,1);
Set(v,fa(u),2);
pushup(v,1);
pushup(fa(u),0);
}
else Set(rs(u),fa(u),2);
clear(u);
}
void splice(int u)
{
splay(u,1);int f=fa(u);
splay(f,0);pushdown(u,1);
if(rs(f))
{
swap(fa(ms(u)),fa(rs(f)));
swap(ms(u),rs(f));
}
else del(u);
pushup(u,1);
pushup(f,0);
}
void access(int u)
{
splay(u,0);
int tmp=u;
if(rs(u))
{
int v=getid();
Set(ms(u),v,0);
Set(rs(u),v,2);
rs(u)=0;Set(v,u,2);
pushup(v,1);
pushup(u,0);
}
while(fa(u))
{
splice(fa(u));
u=fa(u);
pushup(u,0);
}
splay(tmp,0);
}
void makeroot(int u){access(u);pushlazyr(u);}
void updater(int u){makeroot(rt=u);}
void expose(int u,int v){makeroot(u);access(v);}
void link(int u,int v)
{
access(u);
makeroot(v);
Set(v,u,1);
pushup(u,0);
}
int cut(int u)
{
access(u);int v=ls(u);
while(rs(v)){pushdown(v,0);v=rs(v);}
ls(u)=fa(ls(u))=0;
pushup(u,0);
return v;
}
int findroot(int u)
{
access(u);
while(ls(u)){pushdown(u,0);u=ls(u);}
splay(u,0);
return u;
}
void updatef(int u,int v)
{
if(u==v||u==rt)return;
int x=cut(u);
if(findroot(u)==findroot(v))link(u,x);
else link(u,v);
makeroot(rt);
}
void updatep(int u,int v,Lazy w)
{
expose(u,v);
pushlazyp(v,w);
makeroot(rt);
}
void updates(int u,Lazy x)
{
access(u);
pushlazys(ms(u),x);
w(u)=w(u)*x.mul+x.add;
}
node queryp(int u,int v)
{
expose(u,v);
node tmp=sump(v);
makeroot(rt);
return tmp;
}
node querys(int u)
{
access(u);
node tmp=sums(ms(u))+node(1,w(u),w(u),w(u));
makeroot(rt);
return tmp;
}
int main()
{
cin>>n>>q;cnt=n;
for(int i=1;i<n;i++)cin>>e[i].u>>e[i].v;
for(int i=1,val;i<=n;i++)
{
cin>>val;w(i)=val;
pushup(i,0);
}
for(int i=1;i<n;i++)link(e[i].u,e[i].v);
cin>>rt;updater(rt);
for(int i=1,op,u,v,w;i<=q;i++)
{
cin>>op>>u;
if(op==0||op==5)
{
cin>>w;
updates(u,Lazy(op!=0,w));
}
if(op==1)updater(u);
if(op==2||op==6)
{
cin>>v>>w;
updatep(u,v,{op!=2,w});
}
if(op==3||op==4||op==11)
{
node ans=querys(u);
if(op==3)cout<<ans.mn<<'\n';
if(op==4)cout<<ans.mx<<'\n';
if(op==11)cout<<ans.sum<<'\n';
}
if(op==7||op==8||op==10)
{
cin>>v;
node ans=queryp(u,v);
if(op==7)cout<<ans.mn<<'\n';
if(op==8)cout<<ans.mx<<'\n';
if(op==10)cout<<ans.sum<<'\n';
}
if(op==9)
{
cin>>v;
updatef(u,v);
}
}
}