本地 洛谷IDE都能过 为什么交上去TLE或者RE
查看原帖
本地 洛谷IDE都能过 为什么交上去TLE或者RE
534425
IhpEcVns楼主2025/1/9 23:06
#include<bits/stdc++.h>
#define M(x,y)d[x]<d[y]?x:y;
using namespace std;
enum{N=1000001};
basic_string<int>g[N];
int64_t a[N],b[N];
int n,m,x,y,o,d[N],s[N],t[N],f[16][N],*p=*f;
void D(int u,int F){
	for(s[u]=1,d[u]=d[p[t[u]=++m]=F]+1;int&v:g[u])
		if(v^F)D(v,u),s[u]+=s[v];
}
int L(int x,int y){
	if(x==y)return x;x=t[x],y=t[y];
	if(x>y)swap(x,y);int o=__lg(y-x++);
	return M(f[o][x],f[o][y-(1<<o)+1])
}
void A(int x,int v){for(int64_t w=d[x]*v;x<N;x+=x&-x)a[x]+=v,b[x]+=w;}
int64_t Q(int x,int w){int64_t r{};for(;x;x&=x-1)r+=b[x]-a[x]*w;return r;}
int main(){
	for(cin>>n;--n;g[x]+=y,g[y]+=x)cin>>x>>y,++x,++y;D(1,0);cin>>m;
	for(int i=0;i<15;++i)for(int j=1;j+(1<<i)<N;++j)
		f[i+1][j]=M(f[i][j],f[i][j+(1<<i)]);
	for(char c;m--;)if(cin>>c>>x,++x,c^81)cin>>y>>n,++y,o=L(x,y),
		A(t[x],n),A(t[y],n),A(t[o],-n),A(t[p[o]],-n);
	else cout<<Q(t[x]+s[x]-1,d[x]-1)-Q(t[x]-1,d[x]-1)<<'\n';
}
2025/1/9 23:06
加载中...