一時興起回來寫個一篇 至於之後會不會繼續更新就再說吧
這題是第一次國培的回家作業其中一題（夭壽 上一篇文的時候我還沒進二階www）
重心剖分總之還是不太熟 寫了大概四個小時才寫掉
[Tree Coordinates](https://www.hackerrank.com/contests/world-codesprint-8/challenges/tree-coordinates/problem)
### 題目： 定義樹上的距離$d(x,y)$就是會經過的邊數， 那麼對於兩個點對$(x1,y1), (x2,y2)$的距離就是$d(x1,x2)+d(y1,y2)$。 給定一棵樹跟一堆點對，求所有點對對當中距離最遠的那個，輸出距離。
樹上點數$N \leq 75000$，點對數量$M \leq 75000$。
### 不負責題解(?)：
那麼對於每個點對$(x,y)$，把y紀錄在x，接下來遍歷一次原樹，在喵點的時候就把所有點對對的x座標的lca為喵點的點對對做過一次(饒舌)
具體來講，我們在增加一個點對的時候，可以在重心樹上y的位置插入一個$dep[x]$的值，在查詢時就可以直接在重心樹上查離查詢的y距離最大的那個值了（這個距離包含樹上距離跟點值的加權）。不過要注意，為了避免查詢到lca實際上小於自己的點對的答案，merge子樹時要query完一整顆子樹再一次加進去。
另外在重心樹上查詢的時候，可能會需要（至少我要）掃過所有的子樹，這樣如果有太陽就會炸的很慘，所以要建虛點讓每個點的度數保持在定值下。
上code OwO
#define up(x,y) (x=max(x,y))
vector<int> qy[235005],wk,cG[235005];
vector<pair<int,int>> G[235005];
int sz[235005],mxch[235005],ctpa[235005],dep[235005],dis[235005],last[235005],dtc[16][235005],ictd[235005],allval[235005],myval[235005],tpval[235005];
bitset<235005> inct;
void dfs1(int now,int pa){
wk.pb(now);
for(pair<int,int> p:G[now]){
if(inct[p.first] || p.first==pa)continue;
dis[p.first]=dis[now]+p.second;
dfs1(p.first,now);
sz[now]+=sz[p.first];
mxch[now]=max(mxch[now],sz[p.first]);
}
++sz[now];
}
void dfs1_5(int now,int pa,int dep,int nowd){
dtc[dep][now]=nowd;
for(pair<int,int> p:G[now]){
if(p.first==pa)continue;
if(inct[p.first])continue;
dfs1_5(p.first,now,dep,nowd+p.second);
}
}
int cd(int now,int pa,int dep){
dfs1(now,now);
int cen=-1;
for(int i:wk)if(max(mxch[i],int(wk.size())-sz[i])<=int(wk.size())/2)cen=i;
dfs1_5(cen,cen,dep,0);
ictd[cen]=dep;
ctpa[cen]=pa;
inct[cen]=1;
for(int i:wk){
sz[i]=mxch[i]=0;
}
wk.clear();
for(pair<int,int> p:G[cen]){
if(inct[p.first])continue;
dis[p.first]=p.second;
int chcen=cd(p.first,cen,dep+1);
cG[cen].pb(chcen);
}
return cen;
}
void dfs2(int now,int pa){
for(pair<int,int> p:G[now]){
if(p.first==pa)continue;
dep[p.first]=dep[now]+p.second;
dfs2(p.first,now);
sz[now]+=sz[p.first];
}
sz[now]+=qy[now].size();
}
set<int> _add_modify_point;
void clearct(){
for(int i:_add_modify_point){
allval[i]=-999999;
tpval[i]=-999999;
myval[i]=-999999;
}
_add_modify_point.clear();
}
void add(int x,int v){
int ox=x,prv=x;
up(myval[x],v);
x=ctpa[x];
while(x){
up(tpval[prv],v+dtc[ictd[x]][ox]);
up(allval[x],v+dtc[ictd[x]][ox]);
_add_modify_point.insert(x);
_add_modify_point.insert(prv);
prv=x;
x=ctpa[x];
}
}
int query(int x,int v=-999999){
int prv=x,ox=x;
v=max(v,allval[x]);
v=max(v,myval[x]);
x=ctpa[x];
while(x){
for(int cch:cG[x]){
if(cch==prv)continue;
v=max(v,dtc[ictd[x]][ox]+tpval[cch]);
}
v=max(v,dtc[ictd[x]][ox]+myval[x]);
prv=x;
x=ctpa[x];
}
return v;
}
int ans;
vector<pair<int,int>> *dfs3(int now,int pa,bool clean){
sort(G[now].begin(),G[now].end(),[&](const pair<int,int> &a,const pair<int,int> &b){
if(b.first==pa)return true;
if(a.first==pa)return false;
return sz[a.first]<sz[b.first]; });
vector<vector<pair<int,int>>*> rec;
for(pair<int,int> p:G[now]){
if(p.first==pa){
__is_end:;
vector<pair<int,int>>* rt;
if(rec.size()){
rt=rec.back();
rec.pop_back();
}
else rt=new vector<pair<int,int>>();
for(auto *v:rec){
for(auto &p:*v){
int Q=query(p.second);
ans=max(ans,Q+dep[p.first]-dep[now]*2);
}
for(auto &p:*v){
add(p.second,dep[p.first]);
}
}
for(auto &sec:qy[now]){
int Q=query(sec);
ans=max(ans,Q-dep[now]);
}
for(auto &sec:qy[now]){
add(sec,dep[now]);
}
for(auto *v:rec){
if(v->size()>rt->size())swap(rt,v);
for(auto &p:*v)rt->pb(p);
delete v;
}
for(auto &sec:qy[now]){
rt->eb(now,sec);
}
return rt;
}
else{
clearct();
vector<pair<int,int>> *rt=dfs3(p.first,now,p!=G[now].back());
rec.pb(rt);
if(p==G[now].back())goto __is_end;
}
}
assert(0);
}
int main(){
CPPinput;
int n,m; cin>>n>>m;
for(int i=1;i<=n;++i)last[i]=i;
int N=n;
for(int i=1,u,v;i<n;++i){
cin>>u>>v;
int nu=++N,nv=++N;
G[last[u]].eb(nu,0); G[last[v]].eb(nv,0);
G[nu].eb(last[u],0); G[nv].eb(last[v],0);
G[nu].eb(nv,1); G[nv].eb(nu,1);
last[u]=nu, last[v]=nv;
}
int root=cd(1,0,1);
while(m--){
int x,y; cin>>x>>y;
qy[x].pb(y);
}
dep[1]=1;
dfs2(1,1);
dfs3(1,1,0);
cout<<ans<<endl;
}
順便還花了一個小時在搞新的style.... 看起來總算是值得了(?
沒有留言:
張貼留言