QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133661#4941. Tree BeautyPhantomThreshold#WA 252ms74004kbC++202.9kb2023-08-02 12:34:022023-08-02 12:34:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 12:34:03]
  • 评测
  • 测评结果:WA
  • 用时:252ms
  • 内存:74004kb
  • [2023-08-02 12:34:02]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 210000;
const int maxd = 18;

int n,Q;
vector<int>E[maxn];
int dfn[maxn],dfi,dep[maxn],siz[maxn];
int fa[maxn][maxd], num[maxn][maxd];
void dfs(const int x)
{
	for(int i=1;i<maxd;i++) fa[x][i]= fa[ fa[x][i-1] ][i-1];
	
	dfn[x]=++dfi;
	siz[x]=1;
	num[x][0]=1;
	for(auto y:E[x]) 
	{
		dep[y]=dep[x]+1;
		fa[y][0]=x;
		dfs(y);
		siz[x]+=siz[y];
		
		for(int d=0;d+1<maxd;d++) num[x][d+1]+=num[y][d];
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=maxd-1;i>=0;i--) if( dep[x]-dep[y]>=(1<<i) )
		x=fa[x][i];
	if(x==y) return x;
	for(int i=maxd-1;i>=0;i--) if( fa[x][i]!=fa[y][i] )
		x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

struct node
{
	int i,op,x,y,k;
}q[maxn]; int ans[maxn];

int t[maxn],tp;
inline bool cmp(const int x,const int y){ return dfn[x]<dfn[y]; }

vector<int>e[maxn];
vector<int>upd[maxn],query[maxn];
int ff[maxn];
int sum1[maxn];
int adDep[maxn];
void solve(const int x)
{
	for(auto i:upd[x])
	{
		if(q[i].k==1) sum1[x]+=q[i].y;
		else
		{
			int temp=q[i].y;
			for(int d=0;temp!=0;d++)
			{
				adDep[dep[x]+d]+=temp;
				temp/=q[i].k;
			}
		}
	}
	if(query[x].empty()==false)
	{
		int sum= sum1[x]*siz[x];
		for(int d=0;d<maxd;d++)
			sum+= adDep[dep[x]+d]*num[x][d];
		for(auto i:query[x]) ans[i]+=sum;
	}
	for(auto y:e[x])
	{
		sum1[y]+=sum1[x];
		solve(y);
	}
	
	for(auto i:upd[x])
	{
		//if(q[i].k==1) sum1[x]+=q[i].y;
		//else
		if(q[i].k!=1)
		{
			int temp=q[i].y;
			for(int d=0;temp!=0;d++)
			{
				adDep[dep[x]+d]-=temp;
				temp/=q[i].k;
			}
		}
	}
}
void cdq(const int l,const int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	
	tp=0;
	for(int i=l;i<=r;i++) t[++tp]=q[i].x;
	sort(t+1,t+tp+1,cmp);
	tp= unique(t+1,t+tp+1)-t-1;
	
	for(int i=tp;i>1;i--) t[++tp]=lca(t[i],t[i-1]);
	sort(t+1,t+tp+1,cmp);
	tp= unique(t+1,t+tp+1)-t-1;
	
	for(int i=1;i<=tp;i++)
	{
		int x=t[i];
		vector<int>_,__,___;
		e[x].swap(_);
		upd[x].swap(__);
		query[x].swap(___);
		ff[x]=0;
		sum1[x]=0;
	}
	int rt=t[1],now=rt;
	for(int i=2;i<=tp;i++)
	{
		int y=t[i];
		while( !( dfn[now]<=dfn[y] && dfn[y]<dfn[now]+siz[now] ) )
			now=ff[now];
		ff[y]=now;
		e[now].push_back(y);
		now=y;
	}
	for(int i=l;i<=mid;i++) if(q[i].op==1)
		upd[q[i].x].push_back(i);
	for(int i=mid+1;i<=r;i++) if(q[i].op==2)
		query[q[i].x].push_back(i);
	
	solve(rt);
	
	cdq(l,mid); cdq(mid+1,r);
}

signed main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n>>Q;
	for(int i=2;i<=n;i++)
	{
		int p; cin>>p;
		E[p].push_back(i);
	}
	dep[1]=1; dfs(1);
	
	for(int i=1;i<=Q;i++)
	{
		q[i].i=i;
		cin>>q[i].op;
		if(q[i].op==1) cin>>q[i].x>>q[i].y>>q[i].k;
		else cin>>q[i].x;
	}
	cdq(1,Q);
	
	for(int i=1;i<=Q;i++) if(q[i].op==2)
		cout<<ans[i]<<'\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 39868kb

input:

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

output:

245
97
99

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 33480kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 252ms
memory: 74004kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
0
672469600
0
1987509504
0
1681174000
0
0
3026369500
6233535100
6987949855
3856977000
14196952001
11377817000
10186774000
10394197000
9287941000
7069235348
7999042783
0
11118575600
11569594000
15377930450
5835119847
745421000
14142751700
13367272344
9835948365
2981684000
6202227015
4582682500
53...

result:

wrong answer 1st lines differ - expected: '1818724600', found: '0'