C/C++教程
「CTSC2018」暴力写挂
本文主要是介绍「CTSC2018」暴力写挂，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
emmm感觉就是通道的弱化版，就是第一步要想到
description
给两棵树，\(T\)和\(T'\)，求对于所有\(x\),\(y\)，\(depth(x)+depth(y)-(depth(lca(x,y))+depth'(lca'(x,y)))\)的最大值。
solution
两个lca不好处理，考虑把第一个转化为距离。
即：\(\frac{1}{2} *(depth(x)+depth(y)+dist(x,y)-2depth'(lca'(x,y)))\)
这样就老套路了，\(T\)上边分治，\(T'\)上建虚树，枚举\(lca\)，然后相当于找两个在不同集合点的点权和最大值，dp即可。
注意两点：
1.虚树上会有虚点（不要算进去了，其实算进去不会错因为是全集的最大值）
2.\(x\)可以等于\(y\)
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=366666;
const int N=M<<1;
const ll inf=1e18;
namespace IO {
char buf[1<<23],*p1=buf,*p2=buf;
// #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll rd() {
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
}
int n,pos[N],cnt,col[N],lg[N],tp,tt;
ll dis[N],d1[N],d2[N];
namespace T2 {
int nxt[N],In[N],Time,to[N],head[N],ecnt,Nxt[N],To[N],Head[N],Ecnt,dep[N],dfn[N],mnd[N][20],st[N],C[N][20];
ll Len[N],dp[N][3];
void Add_edge(int u,int v,ll w) {
Nxt[++Ecnt]=Head[u];To[Ecnt]=v;Len[Ecnt]=w;Head[u]=Ecnt;
Nxt[++Ecnt]=Head[v];To[Ecnt]=u;Len[Ecnt]=w;Head[v]=Ecnt;
}
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
void _pp(int u,int fa) {
dfn[In[u]=++Time]=u;
for(int i=Head[u];i;i=Nxt[i]) {
int v=To[i];if(v==fa)continue;
dep[v]=dep[u]+1;d2[v]=d2[u]+Len[i];
_pp(v,u);
dfn[++Time]=u;
}
}
void _ST() {
for(int i=1;i<=Time;i++) mnd[i][0]=dep[dfn[i]],C[i][0]=dfn[i];
for(int j=1;j<=lg[Time];j++) {
int s=1<<j;
for(int i=1,up=Time-s+1;i<=up;i++) {
int _i(i+(s>>1));
if(mnd[i][j-1]<mnd[_i][j-1]) {mnd[i][j]=mnd[i][j-1];C[i][j]=C[i][j-1];}
else {mnd[i][j]=mnd[_i][j-1];C[i][j]=C[_i][j-1];}
}
}
}
int Lca(int u,int v) {
u=In[u];v=In[v];
if(u>v)swap(u,v);
int k=lg[v-u+1],_ss=v-(1<<k)+1;
return (mnd[u][k]<=mnd[_ss][k])?C[u][k]:C[_ss][k];
}
void init() {
lg[1]=0;for(int i=2;i<=(n<<1);i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<n;i++) {int u=IO::rd(),v=IO::rd();ll w=IO::rd();Add_edge(u,v,w);}
_pp(1,0);_ST();
}
bool cmp(int u,int v){return In[u]<In[v];}
void Build_T() {
sort(pos+1,pos+1+cnt,cmp);
st[tp=1]=1;int tmp=cnt;pos[++cnt]=1;
for(int i=1;i<=tmp;i++) {
int x(pos[i]);
if(x==1)continue;
int c=Lca(st[tp],x);
if(c!=st[tp]) {
// printf("c=%d(%d)\n",c,col[c]);
if(!col[c]) {pos[++cnt]=c;}
while(In[st[tp-1]]>In[c]) {add_edge(st[tp-1],st[tp]);tp--;}
if(c!=st[tp-1]) {add_edge(c,st[tp]);st[tp]=c;}
else {add_edge(c,st[tp--]);}
}
st[++tp]=x;
}
while(tp>1) {add_edge(st[tp-1],st[tp]);tp--;}
}
ll Mx;
void DP(int u) {
if(col[u]==1) {dp[u][1]=d1[u]+dis[u];dp[u][2]=-inf;}
else if(col[u]==2){dp[u][1]=-inf;dp[u][2]=d1[u]+dis[u];}
else dp[u][1]=dp[u][2]=-inf;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
DP(v);
Mx=max(Mx,max(dp[u][2]+dp[v][1],dp[u][1]+dp[v][2])-2*d2[u]);
dp[u][1]=max(dp[u][1],dp[v][1]);dp[u][2]=max(dp[u][2],dp[v][2]);
}
}
ll solve() {
Build_T();
Mx=0;DP(1);
ecnt=0;
while(cnt) {head[pos[cnt]]=col[pos[cnt]]=0;cnt--;}
return Mx;
}
}
ll ans=0;
namespace T1 {
bool vis[N];
int sz[N],nxt[N<<1],to[N<<1],head[N],ecnt=1,Nxt[N],To[N],Head[N],Ecnt,nd,dep[N],rt,we,op;
ll len[N<<1],Len[N];
void Add_edge(int u,int v,ll w) {
// printf("!%d %d %lld\n",u,v,w);
Nxt[++Ecnt]=Head[u];To[Ecnt]=v;Len[Ecnt]=w;Head[u]=Ecnt;
Nxt[++Ecnt]=Head[v];To[Ecnt]=u;Len[Ecnt]=w;Head[v]=Ecnt;
}
void add_edge(int u,int v,ll w) {
nxt[++ecnt]=head[u];to[ecnt]=v;len[ecnt]=w;head[u]=ecnt;
nxt[++ecnt]=head[v];to[ecnt]=u;len[ecnt]=w;head[v]=ecnt;
}
void _to2(int u,int fa) {
int lst=0;
for(int i=Head[u];i;i=Nxt[i]) {
int v=To[i];if(v==fa)continue;
_to2(v,u);
if(!lst) {add_edge(u,v,Len[i]);lst=u;}
else {nd++;add_edge(lst,nd,0);add_edge(nd,v,Len[i]);lst=nd;}
}
}
void _pp(int u,int fa) {
for(int i=Head[u];i;i=Nxt[i]) {
int v=To[i];if(v==fa)continue;
dis[v]=dis[u]+Len[i];_pp(v,u);
}
}
void dfs(int u,int fa,ll D) {
if(u<=n) {pos[++cnt]=u;d1[u]=D;col[u]=op;}
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];if(v==fa||vis[i])continue;
dfs(v,u,D+len[i]);
}
}
void gt_sz(int u,int fa) {
sz[u]=1;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i]; if(v==fa||vis[i])continue;
gt_sz(v,u);sz[u]+=sz[v];
}
}
void gt_rt(int u,int fa,int tot) {
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];if(v==fa||vis[i])continue;
int w=max(sz[v],tot-sz[v]);
if(we>w) {we=w;rt=i;}
gt_rt(v,u,tot);
}
}
void Divide(int x) {
// tt++;
// printf("%d ",tt);
// printf("!");
gt_sz(x,0);if(sz[x]==1)return;
we=1e9;gt_rt(x,0,sz[x]);
int u=to[rt],v=to[rt^1];
vis[rt]=vis[rt^1]=1;
// printf("!%d: (%d,%d)\n",x,u,v);
op=1;dfs(u,v,0);op=2;dfs(v,u,0);
if(cnt<=1){if(cnt){col[pos[cnt]]=0;cnt=0;}return;}
ans=max(ans,(T2::solve()+len[rt])/2);
Divide(u);Divide(v);
}
void init() {
for(int i=1;i<n;i++) {int u=IO::rd(),v=IO::rd();ll w=IO::rd();Add_edge(u,v,w);}
_pp(1,0);
nd=n;_to2(1,0);
}
}
int main() {
n=IO::rd();
T1::init();T2::init();
T1::Divide(1);
for(int i=1;i<=n;i++) {ans=max(ans,dis[i]-d2[i]);}
printf("%lld",ans);
return 0;
}
这篇关于「CTSC2018」暴力写挂的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
-
在Mac系统上将图片中的文字提取出来有哪些方法？-icode9专业技术文章分享11-22
-
excel 表格中怎么固定一行显示不滚动？-icode9专业技术文章分享11-22
-
怎么将 -rwxr-xr-x 修改为 drwxr-xr-x？-icode9专业技术文章分享11-22
-
在Excel中怎么将小数向上取整到最接近的整数？-icode9专业技术文章分享11-22
-
Excel中常见的取整函数有哪些？-icode9专业技术文章分享11-22
-
错误信息：does not match the actual quantity supplied 提示是什么意思？-icode9专业技术文章分享11-22
-
WebSocket学习：初学者的简单指南11-21
-
获取apk的md5值有哪些方法？-icode9专业技术文章分享11-20
-
xml报文没有传 IdentCode ，为什么正常解析没报错呢？-icode9专业技术文章分享11-20
栏目导航
