QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474238#1163. Another Tree Queries ProblemczcRE 0ms0kbC++235.4kb2024-07-12 16:51:402024-07-12 16:51:41

Judging History

你现在查看的是最新测评结果

  • [2024-07-12 16:51:41]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-12 16:51:40]
  • 提交

answer

#include <bits/stdc++.h>
#define marry return
// #define int long long
#define lowbit(x) (x&-x)
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57)f=ch=='-'?-1:1,ch=getchar();
	while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=getchar();
	return x*f;}
using namespace std;

const int inf=1e18;
const int F=0;
const int mod=114514;


int n,m;
struct node{
	int nx,to;
}w[400005];
int head[200005],t;
void add(int a,int b)	{	w[++t]={head[a],b},head[a]=t;	}


int top;
int siz[200005],dfn[200005];
int pl[200005],pr[200005];
int son[200005],fa1[200005],fa2[200005];
int dep[200005];
long long ds[200005];
inline void shupoudfs1(int s,int fa)
{
	ds[s]=dep[s]=dep[fa]+1;
	fa2[s]=fa;
	siz[s]=1;
	for(int i=head[s];i;i=w[i].nx)
	{
		int vi=w[i].to;
		if(vi==fa)
			continue;
		shupoudfs1(vi,s);
		ds[s]+=ds[vi];
		siz[s]+=siz[vi];
	}
}
inline void shupoudfs2(int s,int fa)
{
	dfn[++top]=s;
	pl[s]=top;
	int mx=0;
	for(int i=head[s];i;i=w[i].nx)
	{
		int vi=w[i].to;
		if(vi==fa)
			continue;
		if(siz[vi]>siz[mx])
			mx=vi;
	}
	if(mx)
		fa1[mx]=fa1[s],
		shupoudfs2(mx,s),
		son[s]=son[mx];
	else
		son[s]=s;
	for(int i=head[s];i;i=w[i].nx)
	{
		int vi=w[i].to;
		if(vi==fa||vi==mx)
			continue;
		fa1[vi]=vi;
		shupoudfs2(vi,s);
	}
	pr[s]=top;
}
void shupou(int st)
{
	shupoudfs1(st,0);
	top=0,fa1[st]=st;
	shupoudfs2(st,0);
}
long long cal(int siz)	{	marry 1ll*siz*(siz-1)/2;	}

struct segment_tree1{
	#define b1 (b<<1)
	#define b2 (b<<1|1)
	#define mid ((l+r)>>1)
	long long sum[800005];
	int tag1[800005],sz[800005];
	long long sumsiz[800005];
	long long tag2[800005],tag3[800005];
	void pushup(int b)	{	sum[b]=sum[b1]+sum[b2];	}
	void pushdown(int b)
	{
		if(tag1[b])
		{
			sum[b1]+=sumsiz[b1]*tag1[b];
			sum[b2]+=sumsiz[b2]*tag1[b];
			tag1[b1]+=tag1[b],tag1[b2]+=tag1[b];
			tag1[b]=0;
		}
		if(tag2[b])
		{
			sum[b1]+=tag2[b]*sz[b1],sum[b2]+=tag2[b]*sz[b2];
			tag2[b1]+=tag2[b],tag2[b2]+=tag2[b];
			tag2[b]=0;
		}
		if(tag3[b])
		{
			sum[b2]+=(cal(sz[b2]))*tag3[b];
			sum[b1]+=(cal(sz[b])-cal(sz[b2]))*tag3[b];
			tag3[b1]+=tag3[b],tag3[b2]+=tag3[b];
			tag2[b1]+=sz[b2]*tag3[b];
			tag3[b]=0;
		}
	}
	void build(int l,int r,int b)
	{
		sz[b]=r-l+1;
		if(l==r)	
			marry sumsiz[b]=siz[dfn[l]],void();
		build(l,mid,b1);
		build(mid+1,r,b2);
		sumsiz[b]=sumsiz[b1]+sumsiz[b2];
	}
	long long query(int l,int r,int b,int ll,int rr)
	{
		if(l>=ll&&r<=rr)
			marry
			// printf("?%d %d %d\n",l,r,sum[b]),
			sum[b];
		pushdown(b);
		long long res=0;
		if(mid>=ll)
			res+=query(l,mid,b1,ll,rr);
		if(mid<rr)
			res+=query(mid+1,r,b2,ll,rr);
		marry res;
	}
	void add1(int l,int r,int b,int ll,int rr,int val)
	{
		// if(b==1)
		// 	printf("1+%d %d %d\n",ll,rr,val);
		if(l>=ll&&r<=rr)
		{
			sum[b]+=sumsiz[b]*val;
			tag1[b]+=val;
			marry;
		}
		pushdown(b);
		if(mid>=ll)
			add1(l,mid,b1,ll,rr,val);
		if(mid<rr)
			add1(mid+1,r,b2,ll,rr,val);
		pushup(b);
	}
	int x,k;
	void add2(int l,int r,int b,int ll,int rr)
	{
		// if(b==1)
		// 	printf("2+%d %d %d %d\n",ll,rr,x,k);
		if(l>=ll&&r<=rr)
		{
			if(k)
			{
				sum[b]+=(cal(rr-l+1)-cal(rr-r))*k;
				tag3[b]+=k;
				tag2[b]+=1ll*(rr-r)*k;
			}
			sum[b]+=1ll*sz[b]*x;
			tag2[b]+=x;
			marry;
		}
		pushdown(b);
		if(mid>=ll)
			add2(l,mid,b1,ll,rr);
		if(mid<rr)
			add2(mid+1,r,b2,ll,rr);
		pushup(b);
	}
	void print(int l,int r,int b)
	{
		printf("%d %d %d\n",l,r,sum[b]);
		if(l==r)
			marry;
		print(l,mid,b1);
		print(mid+1,r,b2);
	}
}T;
long long sumA,sumdep;

void addline(int s,int val)
{
	if(s==0)
		marry;
	T.k=0,T.x=val;
	T.add2(1,n,1,pl[fa1[s]],pl[s]);
	addline(fa2[fa1[s]],val);
}
int lca(int x,int y,int X,int Y)
{
	if(fa1[x]==fa1[y])
	{
		if(dep[x]<dep[y])
			swap(x,y),swap(X,Y);
		T.x=dep[X]-dep[x]+1,T.k=1;
		if(pl[y]<pl[x])
			T.add2(1,n,1,pl[y]+1,pl[x]);
		marry y;
	}
	if(dep[fa1[x]]<dep[fa1[y]])
		swap(x,y),swap(X,Y);
	T.x=dep[X]-dep[x]+1,T.k=1;
	T.add2(1,n,1,pl[fa1[x]],pl[x]);

	marry lca(fa2[fa1[x]],y,X,Y);
}
long long query(int p)
{
	if(p==0)
		marry 0;
	marry T.query(1,n,1,pl[fa1[p]],pl[p])+query(fa2[fa1[p]]);
}

void solve()
{
	int opt=read();
	if(opt==1)
	{
		int x=read(),p=read();
		if(x==p)
		{
			T.add1(1,n,1,1,n,1);
			sumA+=n;
			sumdep+=ds[1];
		}
		else if(pl[p]<=pl[x]&&pr[p]>=pr[x])
		{
			
			T.add1(1,n,1,1,n,1);
			if(pl[p]<pr[p])
				T.add1(1,n,1,pl[p]+1,pr[p],-1);
			sumA+=n-siz[p]+1;
			sumdep+=ds[1]-ds[p]+dep[p];
			addline(p,1-siz[p]);
			
		}
		else
		{
			T.add1(1,n,1,pl[p],pr[p],1);
			sumA+=siz[p];
			sumdep+=ds[p];
			if(fa2[p])
				addline(fa2[p],siz[p]);
		}
	}
	else if(opt==2)
	{
		int x=read(),y=read();
		int LCA=lca(x,y,x,y);
		sumA+=dep[x]+dep[y]-2*dep[LCA]+1;
		sumdep+=cal(dep[x]+1)+cal(dep[y]+1)-2*cal(dep[LCA]+1)+dep[LCA];
		addline(LCA,dep[x]+dep[y]-2*dep[LCA]+1);

	}
	else if(opt==3)
	{
		int p=read();
		long long ans=sumA*dep[p];
		ans+=sumdep;
		ans-=query(p)*2;
		printf("%lld\n",ans);
	}
}

signed main()
{
	freopen("in.in","r",stdin);
	freopen("std.out","w",stdout);

	n=read();
	for(int i=1;i<n;++i)
	{
		int a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	shupou(1);
	T.build(1,n,1);

	// for(int i=1;i<=n;++i)
	// 	printf("%d ",dfn[i]);
	// puts("");
	// for(int i=1;i<=n;++i)
	// 	printf("%d ",siz[dfn[i]]);
	// puts("");

	int t=read();
	while(t--)
		solve();
	marry F;
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

output:


result: