样例过了然而红一片
  • 板块P4842 城市旅行
  • 楼主Piwry
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/5/13 19:52
  • 上次更新2023/11/7 02:31:36
查看原帖
样例过了然而红一片
105254
Piwry楼主2020/5/13 19:52

谁能帮我看看,真找不到错了(

#include <cstdio>
#define ll long long

const int MAXN =5e4+50;

int f[MAXN], c[2][MAXN];
struct qwq{
	ll btf, siz, d, sum;
	ll ep, sum1, sumN;
	bool rev, lzy;
}info[MAXN];

inline bool isroot(int x){ int y =f[x]; return (c[0][y] != x && c[1][y] != x) || y == 0; }

inline bool get(int x){ return c[1][f[x]] == x; }

inline void pushdown(int x, bool rep){
	qwq &rt =info[x];
	int &lcc =c[0][x], &rcc =c[1][x];
	if(rt.rev){
		info[lcc].rev ^=1, info[rcc].rev ^=1;
		c[0][x] ^=c[1][x] ^=c[0][x] ^=c[1][x];
		rt.sum1 ^=rt.sumN ^=rt.sum1 ^=rt.sumN;
		rt.rev =0;
	}
	if(rt.lzy){
		qwq &lc =info[lcc], &rc =info[rcc];
		lc.lzy =1, rc.lzy =1;
		lc.d +=rt.d, rc.d +=rt.d;
		rt.btf +=1ll*rt.d, rt.sum +=1ll*rt.d*rt.siz;
		ll tmp =(1ll*rt.siz*(rt.siz+1))>>1;
		rt.ep +=rt.d*(1ll*tmp*(rt.siz+2)/3);
		rt.sum1 +=rt.d*1ll*tmp, rt.sumN +=rt.d*1ll*tmp;
		rt.lzy =0, rt.d =0;
	}
	if(rep){
		if(lcc) pushdown(lcc, 0);
		if(rcc) pushdown(rcc, 0);
	}
}

inline void pushup(int x){
	qwq &lc =info[c[0][x]], &rc =info[c[1][x]], &rt =info[x];
	rt.siz =lc.siz+rc.siz+1;
	rt.sum =lc.sum+rc.sum+rt.btf;
	rt.ep =lc.ep+rc.ep+1ll*(rc.siz+1)*lc.sum1+1ll*(lc.siz+1)*rc.sumN+1ll*rt.btf*(lc.siz+1)*(rc.siz+1);
	rt.sum1 =lc.sum1+rc.sum1+(lc.siz+1)*1ll*(rt.btf+rc.sum);/**/
	rt.sumN =rc.sumN+lc.sum1+(rc.siz+1)*1ll*(rt.btf+lc.sum);/**/
}

inline void rotate(int x){
	bool r =get(x), r2 =get(f[x]);
	int y =f[x], z =f[y], a =c[!r][x];
	f[x] =z; if(!isroot(y)) c[r2][z] =x;
	f[y] =x; c[!r][x] =y;
	f[a] =y; c[r][y] =a;
	pushup(y);
}

inline void pushall(int x){
	if(!isroot(x)) pushall(f[x]);
	pushdown(x, 1);
}

inline void pushall2(int x){return;
	pushdown(x, 1);
	if(c[0][x]) pushall2(c[0][x]);
	if(c[1][x]) pushall2(c[1][x]);
	pushup(x);
}

inline void splay(int x){
	pushall(x);
	for(; !isroot(x); rotate(x)){
		int y =f[x];
		if(!isroot(y)) rotate((get(y) == get(x)) ? y : x);
	}
	pushup(x);
}

inline void access(int x){
	for(int pre =0; x; pre =x, x =f[x]){
		splay(x);
		c[1][x] =pre;
		pushup(x)/*!*/;
	}
}

inline void setroot(int x){
	access(x), splay(x);
	info[x].rev =1;
	pushall2(x);
}

inline bool connected(int x, int y){
	if(x == y) return 1;
	access(x), splay(x);
	access(y), splay(y);
	return f[x] != 0;
}

inline void link(int x, int y){
	if(connected(x, y)) return;
	setroot(x);
	f[x] =y;
}

inline void cut(int x, int y){
	setroot(x), access(y), splay(x);
	if(c[1][x] != y) return;
	c[1][x] =f[y] =0;
	pushup(x);
}

inline void updata(int x, int y, int dd){
	if(!connected(x, y)) return;
	setroot(x), access(y), splay(y);
	info[y].lzy =1, info[y].d +=dd;
	pushdown(y, 1);
	pushall2(y);
}

int gcd(ll a, ll b){
	while(b ^=a ^=b ^=a %=b) ;
	return a;
}

int C[MAXN];
inline void query(int x, int y){
	if(!connected(x, y)) return (void)puts("-1");
	setroot(x), access(y), splay(y);
	qwq &rt =info[y];
	ll tmp =rt.siz*(rt.siz+1)/2;
	ll anseq =C[rt.siz], g =gcd(rt.ep, tmp);
	printf("%lld/%lld\n", rt.ep/g, tmp/g);
}

inline int read(){
	int x =0; char cc =getchar();
	while(cc < '0' || cc > '9') cc =getchar();
	while(cc >= '0' && cc <= '9') x = (x<<3) + (x<<1) + (48^cc), cc =getchar();
	return x;
}

int main(){
	int n =read(), m =read();
	for(int i =2; i <= n; ++i) C[i] =C[i-1]+i-1;
	for(int i =1; i <= n; ++i){
		qwq &rt =info[i];
		rt.btf =rt.sum =read(), rt.siz =1;
		rt.sum1 =rt.sumN =rt.ep =rt.btf;
	}
	for(int i =0; i < n-1; ++i) link(read(), read());
	for(int i =0; i < m; ++i){
		int op =read(), x =read(), y =read();
		if(op == 1) cut(x, y);
		else if(op == 2) link(x, y);
		else if(op == 3) updata(x, y, read());
		else query(x, y);
	}
}
2020/5/13 19:52
加载中...