#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>
using namespace std;
vector < pair < long long , long long > > Next[200005];
map < long long , long long > all[200005];
set < long long > vis[200005];
long long ans[200005];
long long xx[200005];
long long how[200005];
long long N=0,big=1e18;
long long x,y,root;
pair < long long , long long > A,B;
void F(long long here,long long fa)
{
for(auto i:Next[here])
{
if(i.first!=fa)
{
ans[1]+=i.second;
F(i.first,here);
}
}
}
void F2(long long here,long long fa)
{
for(auto i:Next[here])
{
if(i.first!=fa)
{
ans[i.first]=ans[here]-all[here][i.first]+all[i.first][here];
F2(i.first,here);
}
}
}
pair < long long , long long > F4(long long here,long long fa,long long con)
{
pair < long long , long long > a=make_pair(con,here),b=make_pair(con,here),tt;
for(auto i:Next[here])
{
if(i.first!=fa)
{
tt=F4(i.first,here,con+i.second);
if(tt>a)
{
b=a;
a=tt;
}
else if(tt>b) b=tt;
}
}
big=min(big,ans[here]-(a.first+b.first-2*con));
if(big==ans[here]-(a.first+b.first-2*con))
{
root=here;
x=a.second;
y=b.second;
}
return a;
}
pair < long long , long long > F3(long long here,long long fa,long long con)
{
pair < long long , long long > a=make_pair(con,here),tt;
for(auto i:Next[here])
{
if(i.first!=fa)
{
//printf("bb %lld %lld\n",here,i.first);
tt=F3(i.first,here,con+i.second);
if(tt>a) a=tt;
}
}
big=max(big,a.first);
//printf("%lld %lld\n",here,a.first);
if(big==a.first) x=a.second;
return a;
}
bool F5(long long here,long long fa)
{
vector < pair < long long , long long > > del;
long long ok=0;
if(here==x||here==y) return 1;
else
{
for(auto &i:Next[here])
{
if(i.first==fa) continue;
if(F5(i.first,here))
{
i.second=0;
//all[here][i.first]=1;
ok=1;
}
}
}
return ok;
}
int main()
{
//freopen("03-02.txt","rt",stdin);
long long M,i,j,k,a,b,c,d,where;
scanf("%lld",&N);
for(i=1;i<N;i++)
{
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
Next[a].push_back(make_pair(b,c));
Next[b].push_back(make_pair(a,d));
all[a][b]=c;
all[b][a]=d;
}
for(i=1;i<=N;i++) xx[i]=1e18;
F(1,-1);
F2(1,-1);
how[1]=1e18;
for(i=1;i<=N;i++)
{
how[1]=min(how[1],ans[i]);
if(how[1]==ans[i]) where=i;
}
F4(1,-1,0);
F5(root,-1);
how[2]=big;
//printf("%lld %lld %lld\n",root,x,y);
for(i=3;i<=N;i++)
{
y=-1;
big=0;
F3(root,-1,0);
how[i]=how[i-1]-big;
F5(root,-1);
}
scanf("%lld",&M);
while(M--)
{
scanf("%lld",&a);
printf("%lld\n",how[a]);
}
return 0;
}
Compilation message
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:105:19: warning: unused variable 'j' [-Wunused-variable]
105 | long long M,i,j,k,a,b,c,d,where;
| ^
designated_cities.cpp:105:21: warning: unused variable 'k' [-Wunused-variable]
105 | long long M,i,j,k,a,b,c,d,where;
| ^
designated_cities.cpp:105:31: warning: variable 'where' set but not used [-Wunused-but-set-variable]
105 | long long M,i,j,k,a,b,c,d,where;
| ^~~~~
designated_cities.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
106 | scanf("%lld",&N);
| ~~~~~^~~~~~~~~~~
designated_cities.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
109 | scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
137 | scanf("%lld",&M);
| ~~~~~^~~~~~~~~~~
designated_cities.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%lld",&a);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
23788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Execution timed out |
2077 ms |
62316 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23788 KB |
Output is correct |
| 2 |
Execution timed out |
2090 ms |
62236 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
23788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23788 KB |
Output is correct |
| 2 |
Execution timed out |
2077 ms |
62316 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
23788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
