Tokom takmičenja sam pronašao alternativno rešenje za 70 bodova, koje se zapravo sastoji iz 3 skroz odvojena zadatka, koje ne zahteva nikakvo znanje o centroidima, ne pomaže pri rešavanju za 100 bodova, mada mi je zanimljivo bilo izvođenje, takođe sve tri tehnike koje sam koristio su krajnje nepovezane i sva rešenja se razlikuju od predloženih.
Rešenje kada nema upita
Pretpostavimo da je stablo ukorenjeno u čvoru v, neka je u čvoru i smešteno a_i novčića. Tada je f(v)=\sum_{i=1}^Na_i\cdot{dist(i,v)} broj koraka neophodan za premeštanje svih novčića do čvora v, gde je dist(u,v) udaljenost čvorova u i v u stablu.
Međutim ukoliko bismo ukorenili stablo u svakom od čvorova 1,2,..,N, svaki upit f(i) ima složenost O(N) pa je nakon svakog ažuriranja potrebno O(N^2) operacija.
Ovo se međutim može optimizovati pomoću “rerooting” tehnike. Dakle, neka je dp_v vrednost f(v), a sz_v suma svih a_i u podstablu čvora v, jednim dfs prolazom može se odrediti vrednost dp_u za svako u.
Rešenje kada je stablo bambus
Možemo modelirati stablo kao jednodimenzioni niz a dužine N, gde je a_i broj novčića u čvoru i. Pretpostavimo da je optimalno sve novčiće prebaciti na poziciju i. Ukoliko bismo novčiće prebacili na poziciju i-1 ukupna cena povećava se se za \sum_{j=i}^{N}a_j-\sum_{j=1}^{i-1}a_j. Primetimo da je ova suma, gledano zdesna, opadajuća do nekog k, a potom striktno rastuća. Dakle, moguće je binarnom pretragom ustanoviti optimalan indeks v gde treba prebaciti sve novčiće. Takođe, iz uslova zadatka da svaki čvor mora sadržati bar jedan novčić, ne postoje dva indeksa na kojima je cena prebacivanja jednaka. Dakle nije neophodno rešenje ternarnom pretragom, već korišćenjem nejednakosti se dolazi do zaključka da i binarna pretraga može rešiti zadatak.
Rešenje kada je stablo kompletno binarno stablo
Ovaj slučaj rešavamo time što na svakom nivou stabla održavamo najmanje rešenje, pa potom upoređujemo rešenje za svaki od \log{N} nivoa. Rešenje u korenu stabla je očigledno zbir proizvoda dubina čvorova i broja novčića u njima. Samim tim ažuriranje njegove vrednosti je jednostavno, pa je dovoljno pretprocesiranjem odrediti dubinu svakog čvora i time ažurirati ukupnu sumu.
Koristeći tranzicije iz reroot rešenja, primetimo da su sume na prvom nivou za čvor v jednake sumi u korenu stabla kada im oduzmemo broj novčića u podstablu čvora v, a dodamo sve ostale novčiće van tog podstabla. Sređivanjem nejednakosti dobija se da je promena u čvoru v jednaka tot-2\cdot{sum_v}, gde je tot ukupan broj novčića u celom stablu, a sum_v broj novčića u podstablu čvora v. Analogno dobijamo i rešenje za sve ostale nivoe, odnosno u opštem slučaju, rešenje u čvoru u je ans_{root}+nivo_u\cdot{tot}-2\cdot{\sum_{v-roditelj-u}{sum_v}}, gde su v čvorovi koji su preci čvora u, uključujući i samo u.
Budući da se stablo sastoji od najviše 18 nivoa, a svaka promena utiče samo na roditelje čvora b u koji ubacimo z zlatnika, lako se dobijaju jednakosti po kojima se menjaju sume predaka.
Informacije o svakom nivou možemo čuvati u setu, i u logaritamskom vremenu pronaći minimum na svakom nivou.
Kod je podeljen u tri funkcije, solve_binary za binarno stablo, solve_regular za reroot rešenje i solve_bamboo za bambus.
KOD
#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m,par[N+5],lvl[N+5];
long long a[N+5],sum[N+5],sz[N+5];
vector<int> g[N+5],nodes[25];
set<pair<long long,int>> s[25];
struct bit{
int n;
vector<long long> a;
bit(int n){
this->n=n;
a.resize(n+1);
}
void upd(int v,int val){
for(;v<=n;v+=v&-v)a[v]+=val;
}
long long qry(int v){
long long ret=0;
for(;v;v-=v&-v)ret+=a[v];
return ret;
}
};
int check_bamboo(){
for(int i=1;i<=n;i++)if((int)g[i].size()>2)return 0;
return 1;
}
void dfs_bamboo(int v,int p,vector<int> &bamboo){
bamboo.push_back(v);
for(int u:g[v]){
if(u==p)continue;
dfs_bamboo(u,v,bamboo);
}
}
void solve_bamboo(){
int root=1;
for(int i=1;i<=n;i++)if((int)g[i].size()<=1)root=i;
bit tree(N);
vector<int> bamboo(1);
vector<int> ind(n+1);
dfs_bamboo(root,root,bamboo);
for(int i=1;i<=n;i++)ind[bamboo[i]]=i;
for(int i=1;i<=n;i++)tree.upd(i,a[bamboo[i]]);
int lo=1,hi=n;
int res=1;
for(;lo<=hi;){
int mi=(lo+hi)>>1;
if(2LL*tree.qry(mi)>=tree.qry(n)){
res=mi;
hi=mi-1;
}else{
lo=mi+1;
}
}
cout<<bamboo[res]<<'\n';
for(int i=1;i<=m;i++){
int z,b;cin>>z>>b;
tree.upd(ind[b],z);
int lo=1,hi=n;
int res=1;
for(;lo<=hi;){
int mi=(lo+hi)>>1;
if(2LL*tree.qry(mi)>=tree.qry(n)){
res=mi;
hi=mi-1;
}else{
lo=mi+1;
}
}
cout<<bamboo[res]<<'\n';
}
}
void dfs_regular(int v,int p){
sz[v]=a[v];
sum[v]=0;
for(int u:g[v]){
if(u==p)continue;
dfs_regular(u,v);
sz[v]+=sz[u];
sum[v]+=sum[u]+sz[u];
}
}
void reroot(int v,int p,long long &ans,int &ind){
if(ans>sum[v]){
ind=v;
ans=sum[v];
}else if(ans==sum[v]){
ind=min(ind,v);
}
for(int u:g[v]){
if(u==p)continue;
long long tmp=sum[v]-sum[u]-sz[u];
long long tmp2=tmp+sz[v]-sz[u];
long long tmp3=sz[v]-sz[u];
sum[u]+=tmp2;
sz[u]+=tmp3;
reroot(u,v,ans,ind);
sz[u]-=tmp3;
sum[u]-=tmp2;
}
}
void solve_regular(){
long long ans=1e18;int ind=0;
dfs_regular(1,1);
reroot(1,1,ans,ind);
cout<<ind<<'\n';
}
void dfs_furthest(int v,int p,int cur,int &root,int &dist){
if(dist<=cur){
dist=cur;
root=v;
}
par[v]=p;
for(int u:g[v]){
if(u==p)continue;
dfs_furthest(u,v,cur+1,root,dist);
}
}
void dfs_binary(int v,int p,int d,int root){
lvl[v]=d;
sum[root]+=d*a[v];
sz[v]=a[v];
nodes[d].push_back(v);
for(int u:g[v]){
if(u==p)continue;
dfs_binary(u,v,d+1,root);
sz[v]+=sz[u];
par[u]=v;
}
}
void solve_binary(){
int root=1;
for(int i=1;i<=n;i++){
if((int)g[i].size()==2){
root=i;
}
}
int f1=root,f2=root,d1=0,d2=0;
dfs_furthest(g[root][0],root,0,f1,d1);
dfs_furthest(g[root][1],root,0,f2,d2);
vector<int> diam1,diam2;
for(;f1!=root;){
diam1.push_back(f1);
f1=par[f1];
}
diam1.push_back(root);
for(;f2!=root;){
diam2.push_back(f2);
f2=par[f2];
}
for(int i=(int)diam2.size()-1;i>=0;i--){
diam1.push_back(diam2[i]);
}
root=diam1[(int)diam1.size()/2];
if((int)g[root].size()!=2)root=diam1[(int)diam1.size()/2-1];
dfs_binary(root,root,0,root);
for(int i=1;i<25;i++){
for(int j:nodes[i]){
sum[j]=sum[par[j]]-2*sz[j];
if(i==1)sum[j]-=sum[par[j]];
s[i].insert({sum[j],j});
}
}
pair<long long,int> res={sum[root],root};
for(int j=1;j<25;j++){
if(s[j].empty())continue;
auto it=*s[j].begin();
res=min(res,{it.first+j*sz[root]+sum[root],it.second});
}
cout<<res.second<<'\n';
for(int i=1;i<=m;i++){
int z,b;cin>>z>>b;
sum[root]+=1LL*z*lvl[b];
sz[root]+=z;
for(;b!=root;){
s[lvl[b]].erase({sum[b],b});
sum[b]-=2LL*z*lvl[b];
s[lvl[b]].insert({sum[b],b});
b=par[b];
}
pair<long long,int> res={sum[root],root};
for(int j=1;j<25;j++){
if(s[j].empty())continue;
auto it=*s[j].begin();
res=min(res,{it.first+j*sz[root]+sum[root],it.second});
}
cout<<res.second<<'\n';
}
}
void solve(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
if(m==0){
solve_regular();
}else if(check_bamboo()){
solve_bamboo();
}else{
solve_binary();
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t=1;
for(;t;t--){
solve();
}
return 0;
}