QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#467778#1163. Another Tree Queries ProblemBINYUWA 129ms27488kbC++145.7kb2024-07-08 17:26:022024-07-08 17:26:02

Judging History

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

  • [2024-07-08 17:26:02]
  • 评测
  • 测评结果:WA
  • 用时:129ms
  • 内存:27488kb
  • [2024-07-08 17:26:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
#define ll long long
ll calc(ll st,ll len,ll k)
{
//	cout<<"calc : "<<st<<" "<<len<<" "<<k<<" "<< (2 * st + len * k - k) * len / 2<<"\n";
	return (2 * st + len * k - k) * len / 2;
}
struct Segment_Tree
{
	#define ls id << 1
	#define rs id << 1 | 1
	struct node
	{
		int dep;
		ll len,sum,siz,ad1,ad2,ad3;
	}a[4 * N + 5];
	void pushdown(int id)
	{
		int ad1 = a[id].ad1,ad2 = a[id].ad2,ad3 = a[id].ad3;
		if(ad1)
		{
			a[ls].ad1 += ad1;
			a[ls].sum += ad1 * a[ls].len;
			a[rs].ad1 += ad1;
			a[rs].sum += ad1 * a[rs].len;
			a[id].ad1 = 0;
		}
		if(ad2)
		{
			a[ls].ad2 += ad2;
			a[ls].sum += calc(ad2,a[ls].len,ad2);
			a[rs].ad2 += ad2;
			a[rs].ad1 += a[ls].len * ad2;
			a[rs].sum += a[ls].len * ad2 * a[rs].len;
			a[rs].sum += calc(ad2 + a[ls].len * ad2,a[rs].len,ad2);
			a[id].ad2 = 0;
		}
		if(ad3)
		{
			a[ls].ad3 += ad3;
			a[ls].sum += ad3 * a[ls].siz;
			a[rs].ad3 += ad3;
			a[rs].sum += ad3 * a[rs].siz;
			a[id].ad3 = 0;
		}
	}
	void build(int id,int l,int r)
	{
		a[id].len = r - l + 1;
		if(l == r)return;
		int mid = l + r >> 1;
		build(ls,l,mid);build(rs,mid + 1,r);
	}
	void update(int id,int l,int r,int x,ll siz,int dep)
	{
		if(l == r)
		{
			a[id].siz = siz;
			a[id].dep = dep;
			return;
		}
		int mid = l + r >> 1;
		if(x <= mid)update(ls,l,mid,x,siz,dep);
		else update(rs,mid + 1,r,x,siz,dep);
		a[id].siz = a[ls].siz + a[rs].siz;
		a[id].dep = a[ls].dep + a[rs].dep;
	}
	void add1(int id,int l,int r,int st,int en,ll v)
	{
		if(l >= st&&r <= en)
		{
			a[id].ad1 += v;
			a[id].sum += v * (r - l + 1);
//		cout<<l<<" "<<r<<" : "<<a[id].sum<<"\n";
			return;
		}
		int mid = l + r >> 1;pushdown(id);
		if(st <= mid)add1(ls,l,mid,st,en,v);
		if(en > mid)add1(rs,mid + 1,r,st,en,v);
		a[id].sum = a[ls].sum + a[rs].sum;
//		cout<<l<<" "<<r<<" : "<<a[id].sum<<"\n";
	}
	int add2(int id,int l,int r,int st,int en,ll v)
	{
		if(l >= st&&r <= en)
		{
			a[id].ad1 += v;
			a[id].ad2++;
			a[id].sum += calc(v,r - l + 1,1);
//		cout<<l<<" "<<r<<" :  "<<a[id].sum<<"\n";
			return v + r - l + 1;
		}
		int mid = l + r >> 1;pushdown(id);
		if(st <= mid)v = add2(ls,l,mid,st,en,v);
		if(en > mid)v = add2(rs,mid + 1,r,st,en,v);
		a[id].sum = a[ls].sum + a[rs].sum;
//		cout<<l<<" "<<r<<" :  "<<a[id].sum<<"\n";
		return v;
	}
	void add3(int id,int l,int r,int st,int en,ll v)
	{
		if(l >= st&&r <= en)
		{
			a[id].ad3 += v;
			a[id].sum += v * a[id].siz;
//			cout<<l<<" "<<r<<" :   "<<a[id].sum<<"\n";
			return;
		}
		int mid = l + r >> 1;pushdown(id);
		if(st <= mid)add3(ls,l,mid,st,en,v);
		if(en > mid)add3(rs,mid + 1,r,st,en,v);
		a[id].sum = a[ls].sum + a[rs].sum; 
//		cout<<l<<" "<<r<<" :   "<<a[id].sum<<"\n";
	}
	ll query(int id,int l,int r,int st,int en)
	{
		if(l >= st&&r <= en)return a[id].sum;
		int mid = l + r >> 1;pushdown(id);
		ll res = 0;
		if(st <= mid)res += query(ls,l,mid,st,en);
		if(en > mid)res += query(rs,mid + 1,r,st,en);
		return res;
	}
	int query_dep(int id,int l,int r,int st,int en)
	{
		if(l >= st&&r <= en)return a[id].dep;
		int mid = l + r >> 1;pushdown(id);
		ll res = 0;
		if(st <= mid)res += query_dep(ls,l,mid,st,en);
		if(en > mid)res += query_dep(rs,mid + 1,r,st,en);
		return res;
	}
	#undef ls
	#undef rs 
}st;
int n,q,u,v,op;
int siz[N + 5],son[N + 5],dep[N + 5],f[20][N + 5];
int dfn[N + 5],cntdfn,top[N + 5];
vector <int> e[N + 5];
ll sum1,sum2;
void dfs1(int u,int fa)
{
	siz[u] = 1;
	f[0][u] = fa;
	dep[u] = dep[fa] + 1;
	for(auto v : e[u])
	{
		if(v == fa)continue;
		dfs1(v,u);siz[u] += siz[v];
		if(siz[v] > siz[son[u]])
			son[u] = v;
	}
} 
void dfs2(int u,int t)
{
	top[u] = t;
	dfn[u] = ++cntdfn;
	if(son[u])dfs2(son[u],t);
	for(auto v : e[u])
		if(!dfn[v])dfs2(v,v);
}
int lca(int u,int v)
{
	if(dep[u] < dep[v])swap(u,v);
	for(int i = 18;~i;i--)
		if(dep[f[i][u]] >= dep[v])
			u = f[i][u];
	if(u == v)return u;
	for(int i = 18;~i;i--)
		if(f[i][u] != f[i][u])
			u = f[i][u],v = f[i][u];
	return f[0][u];
}
int jmp(int u,int d)
{
	for(int i = 18;~i;i--)
		if(dep[f[i][u]] > d)
			u = f[i][u];
	return u;
}
ll query(int u)
{
	ll res = 0;
	while(u)
		res += st.query(1,1,n,dfn[top[u]],dfn[u]),
		u = f[0][top[u]];
	return res;
}
void add1(int u,ll v)
{
	while(u)
		st.add1(1,1,n,dfn[top[u]],dfn[u],v),
		u = f[0][top[u]];
}
void add2(int u,int F)
{
	sum1 += dep[u] - dep[F] + 1;
	int now = 1;
	while(top[u] != top[F])
		sum2 += st.query_dep(1,1,n,dfn[top[u]],dfn[u]), 
		now = st.add2(1,1,n,dfn[top[u]],dfn[u],now),
		u = f[0][top[u]];
	sum2 += st.query_dep(1,1,n,dfn[F],dfn[u]);
	st.add2(1,1,n,dfn[F],dfn[u],now); 
}
void add3(int u,ll v)
{
	sum1 += v * siz[u];
	sum2 += v * st.query_dep(1,1,n,dfn[u],dfn[u] + siz[u] - 1);
	st.add3(1,1,n,dfn[u],dfn[u] + siz[u] - 1,v);
	add1(f[0][u],v * siz[u]);
}
int main()
{
	scanf("%d",&n);
	for(int i = 1;i < n;i++)
		scanf("%d %d",&u,&v),
		e[u].push_back(v),e[v].push_back(u);
	dfs1(1,0);dfs2(1,1);
	for(int i = 0;i < 18;i++)
		for(int j = 1;j <= n;j++)
			f[i + 1][j] = f[i][f[i][j]];
	st.build(1,1,n);
	for(int i = 1;i <= n;i++)
		st.update(1,1,n,dfn[i],siz[i],dep[i]);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&op);
		if(op == 1)
		{
			scanf("%d %d",&u,&v);
			if(u == v)add3(1,1);
			else if(lca(u,v) == v)
				add3(1,1),add3(jmp(u,dep[v]),-1);
			else add3(v,1);
		}
		else if(op == 2)
		{
			scanf("%d %d",&u,&v);
			int F = lca(u,v);
			sum2 += dep[F];sum1++;
			if(F != u)add2(u,jmp(u,dep[F]));
			if(F != v)add2(v,jmp(v,dep[F]));
			int cnt = dep[u] + dep[v] - 2 * dep[F] + 1;
			add1(F,cnt);
		}
		else
		{
			scanf("%d",&u);
			ll sum3 = query(u);
			cout<<sum1 * dep[u] + sum2 - 2 * sum3<<"\n";
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 27488kb

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:

1
5

result:

ok 2 number(s): "1 5"

Test #2:

score: -100
Wrong Answer
time: 129ms
memory: 8544kb

input:

200
171 114
50 183
28 68
67 152
139 125
67 55
50 98
106 71
46 42
157 165
42 49
113 12
81 145
105 13
38 96
34 156
24 17
21 191
135 54
174 116
177 157
123 71
95 130
135 193
150 129
25 190
96 93
188 173
90 160
86 187
20 132
199 75
59 195
189 24
40 68
163 83
25 13
73 33
59 50
154 19
146 21
151 67
89 69
...

output:

633
593
574
1240
1778
1090
2240
1640
3436
2836
2744
2624
3840
3028
3843
5453
3541
4408
5319
6741
4809
4572
6162
4165
9469
10810
6984
7198
7191
8466
14221
14529
12680
12993
8100
10861
9954
13607
10221
12323
16380
15786
19082
16279
11272
16222
10641
15138
10695
18930
16056
23247
16401
26279
13733
2453...

result:

wrong answer 1st numbers differ - expected: '826', found: '633'