网站开发公司+重庆,石家庄做网站价格,ai网站设计,国外网页模板题目梗概 给出两棵1为根的树,求\(d[x]d[y]-d[lca(x,y)]-d[lca(x,y)]\)的最大值 解题思路 套路化简之后\((d[x]d[y]dis(x,y)-2*d[lca(x,y)])/2\) 第二棵树上的lca化不掉,所以考虑在第二棵上枚举lca 先说说这题的解法,边分树的合并. 边分和点分有什么区别,边分在合并类似\(d[x]d[…题目梗概 给出两棵1为根的树,求\(d[x]d[y]-d[lca(x,y)]-d[lca(x,y)]\)的最大值 解题思路 套路化简之后\((d[x]d[y]dis(x,y)-2*d[lca(x,y)])/2\) 第二棵树上的lca化不掉,所以考虑在第二棵上枚举lca 先说说这题的解法,边分树的合并. 边分和点分有什么区别,边分在合并类似\(d[x]d[y]dis(x,y)\)这种贡献是很方便,只要记录一条边两端的点集中\(d[x]dis(x,u)\)最大值即可,而点分合并这种贡献时复杂度与度数有关. 所以我们边分治第一棵树,建出边分树之后,遍历第二棵树,每次加入一个点,在边分树上维护答案 考虑左右儿子的答案如何合并,因为边分树是二叉树,像线段树一样合并即可,复杂度\(O(n\) \(log n)\). 边分治:将原图转成二叉树(保证复杂度),每次找左右两端节点数最大值最小的边分开即可. #includecstdio
#includevector
#includecstring
#includealgorithm
#define LL long long
using namespace std;
const int maxn370005;
const LL INF(LL)1e18;
inline int _read(){int num0,f1;char chgetchar();while(ch0||ch9){if (ch-) f-1;chgetchar();}while(ch0ch9) numnum*10ch-48,chgetchar();return f*num;
}
struct jz{int x,y,w;jz(int x0,int y0,int w0):x(x),y(y),w(w){}
};
int lnk[maxn2],son[maxn3],nxt[maxn3],w[maxn3],tot1;
int n,cnt,zo,rx,ry,mi,rh,s[maxn2],rs[maxn3],ls[maxn3],d[maxn2],val[maxn3],fa[maxn3];
int rt[maxn],id,lc[maxn*46],rc[maxn*46],h[maxn*46];
LL rw[maxn*46],lw[maxn*46],dis[23][maxn2],ans-INF;
vectorjz Q;
bool vis[maxn3];
void add(int x,int y,int z){nxt[tot]lnk[x];lnk[x]tot;son[tot]y;w[tot]z;}
void DFS(int x,int fa){int prex;for (int jlnk[x];j;jnxt[j]) if (son[j]!fa){Q.push_back(jz(pre,son[j],w[j]));Q.push_back(jz(pre,cnt,0));precnt;DFS(son[j],x);}
}
void get_ro(int x,int fa,int dep,int lst){s[x]1;for (int jlnk[x];j;jnxt[j]) if (!vis[j]son[j]!fa){dis[dep][son[j]]dis[dep][x]w[j];get_ro(son[j],x,dep,j),s[x]s[son[j]];}int wmax(zo-s[x],s[x]);if (wmi) miw,rxx,ryfa,rhlst;
}
int work(int x,int dep,int sz){if (sz1) return d[x]dep,x;mizosz;int nowcnt;get_ro(x,0,dep,0);vis[rh]vis[rh^1]1;val[now]w[rh];int Xrx,Yry;rs[now]work(Y,dep1,sz-s[X]);ls[now]work(X,dep1,s[X]);fa[ls[now]]fa[rs[now]]now;return now;
}
int add(int x){int lst0,nowx;for (int id[x];i;i--){h[id]fa[now];lw[id]rw[id]-INF; if (nowls[fa[now]]) lw[id]dis[i][x]dis[0][x],lc[id]lst;if (nowrs[fa[now]]) rw[id]dis[i][x]dis[0][x],rc[id]lst;lstid;nowfa[now];}return id;
}
void merge(int x,int y,LL dep){if (!x||!y){xxy;return;}ansmax(ans,lw[x]rw[y]val[h[x]]-dep);ansmax(ans,lw[y]rw[x]val[h[x]]-dep);lw[x]max(lw[x],lw[y]);rw[x]max(rw[x],rw[y]);merge(lc[x],lc[y],dep);merge(rc[x],rc[y],dep);
}
void solve(int x,int fa,LL dep){rt[x]add(x);ansmax(ans,dis[0][x]*2-dep*2);for (int jlnk[x];j;jnxt[j]) if (son[j]!fa){solve(son[j],x,depw[j]);merge(rt[x],rt[son[j]],dep*2);}}
int main(){freopen(exam.in,r,stdin);freopen(exam.out,w,stdout);n_read();cntn;for (int i1;in;i){int x_read(),y_read(),z_read();add(x,y,z);add(y,x,z);}DFS(1,0);memset(lnk,0,sizeof(lnk));tot1;for (int i0;iQ.size();i) add(Q[i].x,Q[i].y,Q[i].w),add(Q[i].y,Q[i].x,Q[i].w);work(1,0,cnt);memset(lnk,0,sizeof(lnk));tot1;for (int i1;in;i){int x_read(),y_read(),z_read();add(x,y,z);add(y,x,z);}solve(1,0,0);printf(%lld\n,ans/2);return 0;
} 转载于:https://www.cnblogs.com/CHNJZ/p/10554011.html
