이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int maxn=2e5+5;
vector<iii> AdjList[maxn];
int n;
int cost[maxn];
int res[maxn];
int sum;
int ans[maxn];
int ans1[maxn];
int path[maxn];
bool used[maxn];
pair<int,int> par[maxn];
void prep(int s=1, int p=-1) {
////cout<<"prep "<<s<<endl;
for(iii tmp: AdjList[s]) {
int u=tmp.fi;
if(u==p) continue;
int w=tmp.se.se;
cost[1]+=w;
prep(u,s);
}
}
void dfs(int s=1, int p=-1) {
////cout<<"dfs "<<s<<endl;
for(iii tmp: AdjList[s]) {
int u=tmp.fi;
if(u==p) continue;
int fw=tmp.se.fi;
int bw=tmp.se.se; // currently bw
cost[u]=cost[s]+fw-bw;
dfs(u,s);
}
}
int in[maxn];
int out[maxn];
int rev[maxn];
int up[maxn][20];
int curt=0;
bool ancestor(int a, int b) {
if(!a) return true;
if(!b) return false;
return in[a]<=in[b]&&out[a]>=out[b];
}
void dfs2(int s, int p=0) {
////cout<<"dfs2 "<<s<<endl;
in[s]=++curt;
//cout<<"in "<<s<<" = "<<in[s]<<endl;
rev[in[s]]=s;
up[s][0]=p;
for(int i=1 ; i<20 ; i++) {
up[s][i]=up[up[s][i-1]][i-1];
////cout<<"up "<<s<<" "<<i<<" = "<<up[s][i]<<endl;
}
for(iii tmp: AdjList[s]) {
int u=tmp.fi;
if(u==p) continue;
int fw=tmp.se.fi;
path[u]=path[s]+fw;
par[u]=ii(s,fw);
////cout<<"par "<<u<<" = "<<s<<" "<<fw<<endl;
////cout<<"u = "<<u<<endl;
dfs2(u,s);
}
out[s]=curt;
//cout<<"out "<<s<<" = "<<out[s]<<endl;
}
int lca(int u, int v) {
////cout<<"lca "<<u<<" "<<v<<" = "<<endl;
if(ancestor(u,v)) return u;
if(ancestor(v,u)) return v;
for(int i=20 ; i>0 ; i--) {
////cout<<"up "<<u<<" "<<i<<" = "<<up[u][i]<<endl;
if(!ancestor(up[u][i],v)) u=up[u][i];
}
////cout<<up[u][0]<<endl;
return up[u][0];
}
// segment tree
pair<int,int> st[maxn*4]; // max
int lz[maxn*4];
void build(int id=1, int tl=1, int tr=n) {
////cout<<"build "<<tl<<" "<<tr<<endl;
if(tl==tr) {
st[id]=make_pair(path[rev[tl]],tl);
lz[id]=0;
////cout<<"st "<<id<<" = "<<st[id].first<<" "<<st[id].second<<'\n';
return;
}
int mid=(tl+tr)/2;
build(id*2,tl,mid);
build(id*2+1,mid+1,tr);
lz[id]=0;
st[id]=max(st[id*2],st[id*2+1]);
////cout<<"st "<<tl<<" "<<tr<<" = "<<st[id].first<<" "<<st[id].second<<'\n';
}
void do_lazy(int id, int tl, int tr) {
if(!lz[id]) return;
if(tl!=tr) {
lz[id*2]+=lz[id];
lz[id*2+1]+=lz[id];
}
st[id].first-=lz[id];
lz[id]=0;
return;
}
void upd(int id, int tl, int tr, int l, int r, int sub) {
////cout<<"update "<<id<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
do_lazy(id,tl,tr);
if(tl>r||tr<l) return;
if(l<=tl&&tr<=r) {
lz[id]+=sub;
do_lazy(id,tl,tr);
return;
}
int mid=(tl+tr)/2;
upd(id*2,tl,mid,l,r,sub);
upd(id*2+1,mid+1,tr,l,r,sub);
st[id]=max(st[id*2],st[id*2+1]);
////cout<<"st "<<tl<<" "<<tr<<" = "<<st[id].first<<" "<<st[id].second<<endl;
}
void sub(int v) {
while(v) {
ii tmp=par[v];
int w=tmp.second;
int p=tmp.first;
if(used[v]) break;
used[v]=1;
upd(1,1,n,in[v],out[v],w);
//cout<<"update "<<v<<" "<<w<<endl;
v=p;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1 ; i<n ; i++) {
int a,b,c,d;
cin>>a>>b>>c>>d;
AdjList[a].push_back(iii(b,ii(c,d))); // forward then backward
AdjList[b].push_back(iii(a,ii(d,c)));
sum+=c; sum+=d;
}
prep(); dfs();
int root=1;
int mx_cost=cost[1];
for(int i=2 ; i<=n ; i++) {
if(cost[i]>mx_cost) {
root=i;
mx_cost=cost[i];
}
}
dfs2(root);
////cout<<"root = "<<root<<endl;
build();
////cout<<"cost "<<root<<" = "<<cost[root]<<endl;
pair<int,int> mn=st[1];
int id1=mn.second;
int val1=mn.first;
int root1=rev[id1];
curt=0;
par[root]=ii(0,0);
path[root]=0;
dfs2(root);
build();
ans[1]=cost[root];
//cout<<"root = "<<root<<endl;
//cout<<"sum = "<<sum<<endl;
//cout<<"ans "<<1<<" = "<<ans[1]<<endl;
for(int i=1 ; i<=n ; i++) used[i]=0;
for(int i=2 ; i<=n ; i++) {
pair<int,int> mn=st[1];
int id=mn.second;
int val=mn.first;
int v=rev[id];
//cout<<"val "<<val<<endl;
//cout<<"v = "<<v<<endl;
////cout<<endl<<"v = "<<v<<endl;
////cout<<"mn = "<<val<<" "<<id<<endl;
ans[i]=ans[i-1]+val;
//cout<<"ans "<<i<<" = "<<ans[i]<<endl<<endl;
sub(v);
}
curt=0;
par[root1]=ii(0,0);
path[root1]=0;
dfs2(root1);
build();
ans1[1]=cost[root1];
//cout<<"root = "<<root<<endl;
//cout<<"sum = "<<sum<<endl;
//cout<<"ans "<<1<<" = "<<ans[1]<<endl;
for(int i=1 ; i<=n ; i++) used[i]=0;
for(int i=2 ; i<=n ; i++) {
pair<int,int> mn=st[1];
int id=mn.second;
int val=mn.first;
int v=rev[id];
//cout<<"val "<<val<<endl;
//cout<<"v = "<<v<<endl;
////cout<<endl<<"v = "<<v<<endl;
////cout<<"mn = "<<val<<" "<<id<<endl;
ans1[i]=ans1[i-1]+val;
//cout<<"ans "<<i<<" = "<<ans[i]<<endl<<endl;
sub(v);
}
int q;
cin>>q;
while(q--) {
int x;
cin>>x;
ans[x]=max(ans[x],ans1[x]);
cout<<sum-ans[x]<<'\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:165:9: warning: unused variable 'val1' [-Wunused-variable]
165 | int val1=mn.first;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |