如何修改用织梦做的网站的模板,笔记模板wordpress,开鲁网站seo转接,绍兴做网站鼎成好久以前开的坑#xff0e; 到今天才填上#xff0e; 首先考虑队第一颗树边分#xff0c;然后分成两个集合\(L,R\)#xff0c;在第二棵树上建出虚树#xff0c;在每个路径\(lca\)处统计答案#xff0c;维护点集的直径只有正权很好维护#xff0e; #include bits/std…好久以前开的坑 到今天才填上 首先考虑队第一颗树边分然后分成两个集合\(L,R\)在第二棵树上建出虚树在每个路径\(lca\)处统计答案维护点集的直径只有正权很好维护 #include bits/stdc.husing namespace std;
typedef long long ll;
typedef pairint,int p;
typedef pairp,p pp;
struct edge{int x;ll w;bool operator (const edge _) const{return x_.xw_.w;}void print(){cerr{x,w} ;}
};
typedef vectoredge vi;
typedef vectorvectoredge vvi;
vi operator (const vi a,const vi b){vi ret(a);ret.insert(ret.end(),b.begin(),b.end());return ret;
}
ostream operator (ostream ou,const p a){return ou[a.first,a.second];
}
const int N100010;
int n;
namespace Tree3{vvi TG;int dep[N],top[N],fa[N],sz[N],son[N];ll dis[N];int getlca(int x,int y){while (top[x]!top[y]){if (dep[top[x]]dep[top[y]]) swap(x,y);yfa[top[y]];}return dep[x]dep[y]?x:y;}ll getdis(int x,int y){return dis[x]dis[y]-2*dis[getlca(x,y)];}void Dfs(int x,int f0){fa[x]f;dep[x]dep[f]1;sz[x]1;for (auto i:TG[x])if (i.x!f){dis[i.x]dis[x]i.w;Dfs(i.x,x);sz[x]sz[i.x];if (sz[i.x]sz[son[x]]) son[x]i.x;}}void Sfd(int x,int tp,int f0){top[x]tp;if (son[x]) Sfd(son[x],tp,x);for (auto i:TG[x])if (i.x!fi.x!son[x]) Sfd(i.x,i.x,x);}void read(){TG.resize(n1);for (int i1; in; i){int x,y;ll w;scanf(%d%d%lld,x,y,w);TG[x].push_back({y,w});TG[y].push_back({x,w});}Dfs(1);Sfd(1,1);}
}
namespace Tree2{const ll INF1e18;vvi TG;int dep[N],col[N],clk,dfn[N],fa[N][17],dtime;ll dis[N],cost[N],ret;pp diameter[N];vectorint E[N];int getlca(int x,int y){if (dep[x]dep[y]) swap(x,y);for (int i16; i0; --i) if (dep[fa[y][i]]dep[x]) yfa[y][i];if (xy) return x;for (int i16; i0; --i) if (fa[y][i]!fa[x][i]) xfa[x][i],yfa[y][i];return fa[x][0];}void Dfs(int x,int f0){fa[x][0]f;for (int i1; i17; i) fa[x][i]fa[fa[x][i-1]][i-1];dfn[x]clk;dep[x]dep[f]1;for (auto i:TG[x])if (i.x!f){dis[i.x]dis[x]i.w;Dfs(i.x,x);}}void read(){//cerrreadbegin2endl;TG.resize(n1);for (int i1; in; i){int u,v;ll w;scanf(%d%d%lld,u,v,w);TG[u].push_back({v,w});TG[v].push_back({u,w});}Dfs(1);//cerrreadend2endl;}bool cmp(const edge a,const edge b){return dfn[a.x]dfn[b.x];}ll calc(int a,int b){if (!(ab)) return (a||b)?-INF:-2*INF;if (ab) return 0;//cerrcalca b cost[a]cost[b]dis[a]dis[b]Tree3::getdis(a,b) dis[a]dis[b]endl;return cost[a]cost[b]dis[a]dis[b]Tree3::getdis(a,b);}ll calc(const p a,const p b){return max(max(calc(a.first,b.second),calc(a.first,b.first)),max(calc(a.second,b.first),calc(a.second,b.second)));}p operator (const p a,int b){ll tcalc(a.first,a.second);ll t2calc(a.first,b);ll t3calc(a.second,b);return max(t2,t3)t?p({t2t3?a.first:a.second,b}):a;}p operator (const p a,const p b){return (ab.first)b.second;}pp operator (const pp a,const pp b){return {a.firstb.first,a.secondb.second};}p tr(int x){return {x,x};}int tim,vis[N],faf[N];void dfs(int x){//cerrdfs on virtual tree:x dis[x]endl;diameter[x]{tr(col[x]1?x:0),tr(col[x]1?0:x)};//cerrdiameter[x].first diameter[x].second retendl;for (auto i:E[x]){dfs(i);retmax(ret,calc(diameter[x].first,diameter[i].second)-dis[x]*2);retmax(ret,calc(diameter[x].second,diameter[i].first)-dis[x]*2);//cerraftmergex i diameter[x].first diameter[x].second ret dis[x]endl;diameter[x]diameter[x]diameter[i];}faf[x]0;E[x].clear();//cerrendix diameter[x].first diameter[x].second retendl;}ll build_virtual_tree(vi a){sort(a.begin(),a.end(),cmp);stackint s;int rta[0].x;ret0;vectorint vim;for (auto i:a){vim.push_back(i.x);if (s.size()){int lcagetlca(s.top(),i.x);vim.push_back(lca);//cerrbuildi.x lca faf[1]endl;if (dep[lca]dep[rt]) rtlca;while (dep[faf[s.top()]]dep[lca]) s.pop();bool cd(faf[s.top()]!lca);if (cd) faf[lca]faf[s.top()];if (s.top()!lca) faf[s.top()]lca;s.pop();if (cd) s.push(lca);faf[i.x]lca;}s.push(i.x);}tim;for (auto i:vim)if (vis[i]tim){vis[i]tim;//cerrfai faf[i]endl;E[faf[i]].push_back(i);}//cerrESZEE[rt].size() rtendl;//exit(0);dfs(rt);return ret;}ll main(vi u,vi v){if (!(u.size()v.size())) return -INF;dtime;for (auto i:u){col[i.x]dtime;cost[i.x]i.w;}dtime;for (auto i:v){col[i.x]dtime;cost[i.x]i.w;}return build_virtual_tree(uv);}
}
namespace Tree1{vvi G,TG;int sz[N1];int aa,bb,cnt,val;ll ans,ww;void dfs(int x,int f){for (auto i:TG[x])if (i.x!f) dfs(i.x,x);int nowx;for (auto i:TG[x])if (i.x!f){G[now].push_back({i.x,i.w});G[i.x].push_back({now,i.w});//cerrcdrnow i.x i.wendl;cnt;G[now].push_back({cnt,0});G[cnt].push_back({now,0});//cerrcarnow cnt 0endl;nowcnt;}}void getsz(int x,int f0){sz[x]1;for (auto i:G[x])if (i.x!f){getsz(i.x,x);sz[x]sz[i.x];}}void dfs(int x,int f,ll len){if (max(val-sz[x],sz[x])max(val-sz[aa],sz[aa])){aax;bbf;wwlen;}for (auto i:G[x])if (i.x!f) dfs(i.x,x,i.w);}void Getpoint(int x,vi g,int f0,ll dis0){if (xn) g.push_back({x,dis});for (auto i:G[x]) if (i.x!f) Getpoint(i.x,g,x,disi.w);}void BF(int x){//cerrBFxendl;getsz(x);//cerrgetendendl;aax;bb0;valsz[x];if (val1) return;//cerrdfsbeginendl;dfs(x,0,0);//cerrdfsendaa bb ww (find(G[aa].begin(),G[aa].end(),edge{bb,ww})G[aa].end())endl;G[aa].erase(find(G[aa].begin(),G[aa].end(),edge{bb,ww}));G[bb].erase(find(G[bb].begin(),G[bb].end(),edge{aa,ww}));//cerr???endl;vi u,v;Getpoint(aa,u);Getpoint(bb,v);//cerrU:endl;//for (auto i:u) i.print();//cerrendlV:endl;//for (auto i:v) i.print();//cerrendlWhats the edge:aa bb wwendl;ansmax(ans,Tree2::main(u,v)ww);//cerrinthisans:ansendl;//exit(0);int tmpbb;BF(aa);BF(tmp);}void main(){scanf(%d,n);TG.resize(n1);G.resize(2*n);cntn;for (int i1; in; i){int u,v;ll w;scanf(%d%d%lld,u,v,w);TG[u].push_back({v,w});TG[v].push_back({u,w});}Tree2::read();Tree3::read();/*for (int i1; in; i)for (int j1; jn; j)cerri j Tree3::getdis(i,j)endl;*/dfs(1,0);BF(1);coutans;}
}
int main(){Tree1::main();
} 转载于:https://www.cnblogs.com/Yuhuger/p/10575258.html
