QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884254#10066. Many Pairsguleng2007#0 1176ms45072kbC++202.6kb2025-02-05 22:51:282025-02-05 22:51:29

Judging History

This is the latest submission verdict.

  • [2025-02-05 22:51:29]
  • Judged
  • Verdict: 0
  • Time: 1176ms
  • Memory: 45072kb
  • [2025-02-05 22:51:28]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+5;

vector <int> g[N];
int sz[N], fa[N], dep[N], son[N];

void dfs1(int x)
{
	sz[x]=1;
	for(auto to:g[x])
		if(to!=fa[x])
		{
			fa[to]=x;
			dep[to]=dep[x]+1;
			dfs1(to);
			sz[x] += sz[to];
			if(sz[to]>sz[son[x]])
				son[x]=to;
		}
}

int top[N], dfsn[N], point[N], Indx;

void dfs2(int x,int t)
{
	top[x]=t, dfsn[x]=++Indx, point[Indx]=x;
	if(son[x])
		dfs2(son[x],t);

	for(auto to:g[x])
		if(to!=fa[x] && to!=son[x])
			dfs2(to,to);
}

int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);

		x=fa[top[x]];
	}

	if(dep[x]<dep[y])
		return x;
	return y;
}

struct node
{
	int x,y,c;
};

vector <node> vec[N];
int p[N], sum[N], ans[N], tot[N], out[N], alltot;
map <pair<int,int>,int> Edge;

int getfa(int x)
{
	if(x!=p[x])
		p[x]=getfa(p[x]);
	return p[x];
}

void merge(int x,int y)
{
	int fax=getfa(x), fay=getfa(y);
	p[fax]=fay;
}

void dfs3(int x)
{
	for(auto to:g[x])
		if(to!=fa[x])
		{
			dfs3(to);
			sum[x] += sum[to];
			tot[x] += tot[to];
		}

	Edge.clear();
	for(auto p:vec[x])
	{
		sum[x] += p.c;
		if(p.x==x || p.y==x)
			sum[getfa(p.x+p.y-x)] += p.c;
		else
		{
			out[getfa(p.x)] += p.c;
			out[getfa(p.y)] += p.c;
			Edge[make_pair(min(getfa(p.x),getfa(p.y)),max(getfa(p.x),getfa(p.y)))] += p.c;
		}
	}

	vector <int> val;
	for(auto to:g[x])
		if(to!=fa[x])
			val.push_back(sum[to]);

	sort(val.begin(),val.end(),greater<int>());

	if(val.size()>=2)
		ans[x]=max(ans[x],val[0]+val[1]);
	else if(val.size())
		ans[x]=max(ans[x],val[0]);

	for(auto p:Edge)
		ans[x]=max(ans[x],sum[p.first.first]+sum[p.first.second]+p.second);

	vector<int> son;
	for(auto to:g[x])
		if(to!=fa[x])
			son.push_back(to);

	if(!son.size())
		ans[x]=alltot;
	else
	{
		for(auto to:son)
		{
			int val=alltot;
			for(auto oth:son)
				if(oth!=to)
					val -= tot[oth];
			val += sum[x]-sum[to]-out[to];
			ans[x]=max(ans[x],val);
		}
	}

	for(auto to:g[x])
		if(to!=fa[x])
			merge(to,x);
}

signed main()
{
	int n,k;
	cin >> n >> k;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld %lld",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	dep[1]=1;
	dfs1(1);
	dfs2(1,1);

	for(int i=1;i<=k;i++)
	{
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		alltot += c;
		if(a==b)
			assert(0);

		tot[a] += c, tot[b] += c;
		vec[lca(a,b)].push_back((node){a,b,c});
	}

	for(int i=1;i<=n;i++)
		p[i]=i;

	dfs3(1);

	for(int i=1;i<=n;i++)
		printf("%lld ",ans[i]);
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 12060kb

input:

50 50
1 20
13 1
39 1
12 1
16 1
4 1
9 1
1 17
33 1
1 28
1 46
31 1
1 23
44 1
15 1
1 7
14 1
1 40
1 25
1 34
11 1
6 1
1 30
1 3
42 1
1 48
35 1
27 1
1 45
29 1
10 1
19 1
2 1
38 1
41 1
1 37
1 32
18 1
47 1
26 1
22 1
1 5
1 50
49 1
1 21
43 1
1 8
1 36
24 1
26 20 640
41 45 742
39 15 520
20 18 703
47 16 391
2 19 97...

output:

2373 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 

result:

wrong answer 1st lines differ - expected: '1864 35112 35112 35112 35112 3...2 35112 35112 35112 35112 35112', found: '2373 35112 35112 35112 35112 3... 35112 35112 35112 35112 35112 '

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 11ms
memory: 18832kb

input:

5000 500
1 2035
2103 1
2889 1
3899 1
1 1572
2838 1
1 3608
2582 1
1 2880
201 1
3989 1
1 1300
4071 1
2576 4504
1 3547
1 1145
3878 1
1 3240
1 2047
1 4983
3564 1
4965 4504
1 1305
3217 1
1 4820
2377 1
1640 1
1363 1
1 4731
1 4040
1 3707
3364 1
1 79
1 4968
2679 1
1 3276
1 4709
1 4438
1 3420
1 828
4504 4554...

output:

7355 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 3...

result:

wrong answer 1st lines differ - expected: '7043 332097 332097 332097 3320...097 332097 332097 332097 332097', found: '7355 332097 332097 332097 3320...97 332097 332097 332097 332097 '

Subtask #3:

score: 0
Wrong Answer

Test #15:

score: 17
Accepted
time: 13ms
memory: 18780kb

input:

5000 2000
1 2035
2103 1
2889 1
3899 1
1 1572
2838 1
1 3608
2582 1
1 2880
201 1
3989 1
1 1300
4071 1
2576 4504
1 3547
1 1145
3878 1
1 3240
1 2047
1 4983
3564 1
4965 4504
1 1305
3217 1
1 4820
2377 1
1640 1
1363 1
1 4731
1 4040
1 3707
3364 1
1 79
1 4968
2679 1
1 3276
1 4709
1 4438
1 3420
1 828
4504 455...

output:

2212740 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 13...

result:

ok single line: '2212740 130540162 130540162 13... 130540162 130540162 130540162 '

Test #16:

score: 17
Accepted
time: 1ms
memory: 12800kb

input:

5000 2000
2967 950
1 4700
3353 2511
4023 1
1300 4532
2356 3798
1300 3894
997 4696
999 3080
35 4766
3785 2028
793 2309
63 741
1766 3785
3285 586
3353 867
3730 1
2980 3727
1065 997
2678 2375
2751 1683
4691 1400
2827 2706
1548 4078
1 1376
1443 3224
2629 4159
1552 3353
4536 1300
3103 3632
3368 865
2174 ...

output:

3167789 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 12...

result:

ok single line: '3167789 129909272 129909272 12... 129909272 129909272 129909272 '

Test #17:

score: 0
Wrong Answer
time: 4ms
memory: 15032kb

input:

5000 2000
2967 3037
3043 4700
174 2511
4023 2384
1654 4532
2356 1104
386 3894
2067 4696
999 4577
35 2198
1623 2028
793 3636
63 3998
1766 2649
3285 3906
608 867
3730 247
3566 3727
1065 2247
728 2375
2649 1683
4691 4296
2827 4197
1548 2888
2904 1376
3566 3224
2629 3234
1552 3243
4536 4202
201 3632
241...

output:

129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129741991 129909272 129909272 129803447 129909272 129833295 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 ...

result:

wrong answer 1st lines differ - expected: '129909272 129909272 129909272 ...2 129909272 129909272 129909272', found: '129909272 129909272 129909272 ... 129909272 129909272 129909272 '

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 21
Accepted
time: 11ms
memory: 15200kb

input:

5000 5000
1 2035
2103 1
2889 1
3899 1
1 1572
2838 1
1 3608
2582 1
1 2880
201 1
3989 1
1 1300
4071 1
2576 4504
1 3547
1 1145
3878 1
1 3240
1 2047
1 4983
3564 1
4965 4504
1 1305
3217 1
1 4820
2377 1
1640 1
1363 1
1 4731
1 4040
1 3707
3364 1
1 79
1 4968
2679 1
1 3276
1 4709
1 4438
1 3420
1 828
4504 455...

output:

46132009 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 26490...

result:

ok single line: '46132009 2649064843 2649064843...49064843 2649064843 2649064843 '

Test #22:

score: 21
Accepted
time: 4ms
memory: 12776kb

input:

5000 5000
2967 950
1 4700
3353 2511
4023 1
1300 4532
2356 3798
1300 3894
997 4696
999 3080
35 4766
3785 2028
793 2309
63 741
1766 3785
3285 586
3353 867
3730 1
2980 3727
1065 997
2678 2375
2751 1683
4691 1400
2827 2706
1548 4078
1 1376
1443 3224
2629 4159
1552 3353
4536 1300
3103 3632
3368 865
2174 ...

output:

71850241 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 26492...

result:

ok single line: '71850241 2649293842 2649293842...49293842 2649293842 2649293842 '

Test #23:

score: 0
Wrong Answer
time: 3ms
memory: 13068kb

input:

5000 5000
2967 3037
3043 4700
174 2511
4023 2384
1654 4532
2356 1104
386 3894
2067 4696
999 4577
35 2198
1623 2028
793 3636
63 3998
1766 2649
3285 3906
608 867
3730 247
3566 3727
1065 2247
728 2375
2649 1683
4691 4296
2827 4197
1548 2888
2904 1376
3566 3224
2629 3234
1552 3243
4536 4202
201 3632
241...

output:

2649293842 2649293842 2649293842 2649293842 2646227721 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2645738482 2649293842 2649293842 2645969915 2649293842 2648356916 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 264...

result:

wrong answer 1st lines differ - expected: '2649293842 2649293842 26492938...649293842 2649293842 2649293842', found: '2649293842 2649293842 26492938...49293842 2649293842 2649293842 '

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 1176ms
memory: 45072kb

input:

200000 200000
1861 126068
196536 190176
143836 3918
183352 173153
149804 74098
192775 110127
106287 1861
103451 149418
160851 35753
171988 21209
156996 161848
138469 165694
35753 140239
100453 199546
110790 120346
73215 149224
19332 138469
72674 21209
127832 142648
86197 174308
181332 15643
148621 1...

output:

1640901879 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105...

result:

wrong answer 1st lines differ - expected: '1640901879 105069892770 105069...92770 105069892770 105069892770', found: '1640901879 105069892770 105069...2770 105069892770 105069892770 '