P4565 [CTSC2018]暴力写挂 题解
题面
这题感觉思路比较正常。首先考虑化式子，原式需要在两棵树上分别求 \(lca\)，这很不好。考虑把式子写成
\[\frac{1}{2}\big(dis_1(x,y)+dep_1(x)+dep_1(y)-2\times dep_2(LCA_2(x,y)\big) \]对于这个 \(dis_1\)，很显然的做法就是在第一棵树上点分治。考虑当前连通块，每个点维护一个权值 \(w_u=dep_1(u)+dis_1(u,rt)\)，其中 \(rt\) 是当前连通块的重心。把这些点在第二棵树上建虚树，在虚树上 dp。由于不能统计第一棵树同一子树中的点对，所以需要维护一个最大值，一个次大值，并且保证这两个值不在同一子树中。合并的时候顺便统计答案即可。复杂度 \(2\log\)。
注意一些细节的处理，比如 \(1\) 号点也在虚树上，比如 \(x=y\) 的情况等等。
点击查看代码
inline void clearvector(std::vector &a){std::vector b;std::swap(a,b);}
const int N=3.7e5+13;
struct Edge{int v,w,nxt;};
int n;
ll ans=-LLINF;
namespace tree2{
struct Stack{
int s[N],t;
inline void clear(){s[t=0]=0;}
Stack(){clear();}
inline void push(int x){s[++t]=x;}
inline void pop(){--t;}
inline int ttop(){return s[t-1];}
inline int top(){return s[t];}
inline bool empty(){return !t;}
};
Edge e[N<<1];
int h[N],etot;
inline void add_edge(int u,int v,int w){e[++etot]=(Edge){v,w,h[u]};h[u]=etot;}
inline void readedge(){
for(int i=1;isiz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++dfs_clock;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]] G[N],fuck;
bool vis[N];
inline bool cmp(const int &x,const int &y){return id[x] a){
Stack st;clearvector(fuck);
std::sort(a.begin(),a.end(),cmp);
st.push(1);
for(int i=0,lim=a.size();i1&&id[t] point;
ll d[N],w[N];
void init(int u,int f){
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f)continue;
d[v]=d[u]+e[i].w;
init(v,u);
}
}
void findrt(int u,int f){
siz[u]=1,maxx[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f||vis[v]) continue;
findrt(v,u);
siz[u]+=siz[v];
maxx[u]=max(maxx[u],siz[v]);
}
maxx[u]=max(maxx[u],psum-siz[u]);
if(maxx[u]f[u][0]){
if(g[v][0]!=g[u][0]&&f[u][0]>f[v][1]) f[u][1]=f[u][0],g[u][1]=g[u][0];
else if(f[v][1]>f[u][1]||g[v][0]==g[u][1]) f[u][1]=f[v][1],g[u][1]=g[v][1];
f[u][0]=f[v][0],g[u][0]=g[v][0];
}
else{
if(f[v][0]>f[u][1]&&g[v][0]!=g[u][0]) f[u][1]=f[v][0],g[u][1]=g[v][0];
else if(f[v][1]>f[u][1]&&g[v][1]!=g[u][0]) f[u][1]=f[v][1],g[u][1]=g[v][1];
}
}
}
}
int main(){
// return system("fc data.out wronganswer1.ans"),0;
#ifdef LOCAL
freopen("wronganswer1.in","r",stdin);
// freopen("data.out","w",stdout);
#endif
read(n);
tree1::readedge();tree2::readedge();
tree2::init();
tree1::mian();
for(int i=1;i<=n;++i) ans=max(ans,tree1::d[i]-tree2::dis[i]);
println(ans);
return 0;
}