題目描述

http://uoj.ac/problem/347

題解

解法1

求三棵樹的直徑，看起來非常不可做，但是所有邊權都是正的，可以讓我們想到爬山。

所以我們可以按照BFS求樹的直徑的方法，隨機一個點作為起點，然后BFS一遍，找到在這三棵樹的意義下最遠的那個點，然后繼續爬山。

因為這樣做沒啥正確性，所以再卡一下時間就好了。

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #define get_clock (double)clock()/(double)CLOCKS_PER_SEC*1000.0 #define N 100009 using namespace std; typedef long long ll; ll dis[3][N],n,ans; bool vis[N]; inline ll rd(){ll x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } struct Edge{int head[N],tot;struct ljb{int n,to;ll l;}e[N<<1];inline void add(int u,int v,ll l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=l;} }edge[3]; void dfs(int u,int fa,int tag){for(int i=edge[tag].head[u];i;i=edge[tag].e[i].n)if(edge[tag].e[i].to!=fa){int v=edge[tag].e[i].to;dis[tag][v]=dis[tag][u]+edge[tag].e[i].l;dfs(v,u,tag);} } void BF(){for(int x=1;x<=n;++x){dis[0][x]=dis[1][x]=dis[2][x]=0;dfs(x,0,0);dfs(x,0,1);dfs(x,0,2);for(int i=1;i<=n;++i){ans=max(ans,dis[0][i]+dis[1][i]+dis[2][i]);} } } int main(){srand(19260817);double start=get_clock;n=rd();ll u,v,w;for(int i=1;i<n;++i){u=rd();v=rd();w=rd();edge[0].add(u,v,w);}for(int i=1;i<n;++i){u=rd();v=rd();w=rd();edge[1].add(u,v,w);}for(int i=1;i<n;++i){u=rd();v=rd();w=rd();edge[2].add(u,v,w);}if(n<=3000){BF();}else{while(get_clock-start<=3500){int x=rand()%n+1;while(vis[x])x=rand()%n+1;for(int j=1;j<=9;++j){if(vis[x])break;vis[x]=1;dis[0][x]=dis[1][x]=dis[2][x]=0;dfs(x,0,0);dfs(x,0,1);dfs(x,0,2);ll now=0;for(int i=1;i<=n;++i){ll num=dis[0][i]+dis[1][i]+dis[2][i];ans=max(ans,num);if(num>now){now=num;if(!vis[i])x=i;}} } }}cout<<ans;return 0; }

這樣做可以通過官方數據，但是在UOJ上會被HACK。

解法2

我們考慮對第一棵樹邊分治，設當前的重心邊為i。

那么我們需要最大化的東西就是deep1[x]+deep1[y]+val[i]+dist2(x,y)+dist3(x,y)。

其中xy是當前邊分的塊內點，且分居在i的兩側，我們可以設兩邊的顏色為黑色和白色。

這樣我們相當于給x和y加上了一個權，并且去掉了第一棵樹的LCA的限制。

而且val的影響可以先不討論了。

然后我們考慮對第二顆樹對目前邊分的點建立虛樹。

令value[x]表示deep1[x]+deep2[x]。

然后我們在dfs虛樹的時候枚舉LCA，那么此時我們要最大化的東西就是value[x]+value[y]-2*deep2[lca]+dist3(x,y)，需滿足x和y在LCA的不同子樹中。

然后最后的是個常數，而不用管。

然后value[x]+value[y]+dist3(x,y)這個東西，有點像樹的直徑。

我們可以想象一下，在第三棵樹上的每一個點i我們都往外連出一條出邊連向i'，邊權為value[i]，這樣上面的東西就變成了樹的直徑問題。

有一個結論，有兩個點集，每個點集的直徑為x-y，那么跨越兩個點集的直徑的兩個端點一定在那兩個點集的端點中出現過。

這個結論在邊權非負的條件下成立。

所以我們對黑白兩個點集分別維護直徑，在子樹合并的時候更新答案就好了。

其實想到這里，這道題就不難了，就是碼量有點大。

ZZ錯誤：求LCA倍增寫錯，合并直徑時沒有考慮只有一個點的情況。

代碼

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cmath> #define inf 1e18 #define N 100009 using namespace std; typedef long long ll; int dfn[N],s,n,NTT; inline ll rd(){ll x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } struct node{int tag,x;ll y;inline bool operator <(const node &b)const{return dfn[x]<dfn[b.x];} }a[N]; namespace T3{int head[N],tot,p[20][N<<1],tag[N],lo[N<<1];ll dis[N];struct edge{int n,to;ll l;}e[N<<1];inline void add(int u,int v,ll l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;}void dfs(int u,int fa){p[0][++tag[0]]=u;tag[u]=tag[0];for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){int v=e[i].to;dis[v]=dis[u]+e[i].l;dfs(v,u);p[0][++tag[0]]=u;}}inline int great(int x,int y){return tag[x]>tag[y]?y:x;}inline int getlca(int u,int v){int x=tag[u],y=tag[v];if(x>y)swap(x,y);int llo=lo[y-x+1];return great(p[llo][x],p[llo][y-(1<<llo)+1]);}inline void prework(){dfs(1,0);for(int i=1;(1<<i)<=tag[0];++i)for(int j=1;j<=tag[0];++j)p[i][j]=great(p[i-1][j],p[i-1][j+(1<<i-1)]);///!!!!for(int i=2;i<=tag[0];++i)lo[i]=lo[i>>1]+1;}inline ll calc(int x,int y){return dis[x]+dis[y]-2*dis[getlca(x,y)];} } namespace T2{int head[N],tot,p[20][N<<1],tag[N],lo[N<<1],vis[N],st[N],top,rbs[N];ll dis[N],val[N],ans;vector<int>::iterator it;vector<int>vec[N];struct edge{int n,to;ll l;}e[N<<1];inline void add(int u,int v,ll l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;}struct DP{int x[2];inline bool empty(int x,int y){return (!x&&!y);}inline void clear(){x[0]=x[1]=0;}}dp[N][3];void dfs(int u,int f){p[0][++tag[0]]=u;tag[u]=tag[0];dfn[u]=++dfn[0];for(int i=head[u];i;i=e[i].n)if(e[i].to!=f){int v=e[i].to;dis[v]=dis[u]+e[i].l;dfs(v,u);p[0][++tag[0]]=u;}} inline int great(int x,int y){return tag[x]>tag[y]?y:x;}inline int getlca(int u,int v){int x=tag[u],y=tag[v];if(x>y)swap(x,y);int llo=lo[y-x+1];return great(p[llo][x],p[llo][y-(1<<llo)+1]);}inline void prework(){dfs(1,0); for(int i=1;(1<<i)<=tag[0];++i)for(int j=1;j+(1<<i)-1<=tag[0];++j)p[i][j]=great(p[i-1][j],p[i-1][j+(1<<i-1)]);for(int i=2;i<=tag[0];++i)lo[i]=lo[i>>1]+1;}inline ll calc(int x,int y){if(!x||!y)return -inf;return val[x]+val[y]+T3::calc(x,y);}void ddp(int u){if(vis[u])dp[u][vis[u]].x[0]=u;for(int i=0;i<vec[u].size();++i){int v=vec[u][i];ddp(v);for(int i=1;i<=2;++i)for(int j=0;j<2;++j)for(int k=0;k<2;++k){int d=i==1?2:1,x=dp[u][i].x[j],y=dp[v][d].x[k];ans=max(ans,calc(x,y)-2ll*dis[u]);}for(int i=1;i<=2;++i){if(!dp[u][i].x[0]&&!dp[u][i].x[1]){dp[u][i].x[0]=dp[v][i].x[0];dp[u][i].x[1]=dp[v][i].x[1];continue;}if(!dp[v][i].x[0]&&!dp[v][i].x[1])continue;int maxx=dp[u][i].x[0],maxy=dp[u][i].x[1];ll you=calc(maxx,maxy),bian=calc(dp[v][i].x[0],dp[v][i].x[1]);if(bian>you)maxx=dp[v][i].x[0],maxy=dp[v][i].x[1],you=bian;for(int j=0;j<2;++j)for(int k=0;k<2;++k){int x=dp[u][i].x[j],y=dp[v][i].x[k];bian=calc(x,y);if(bian>you)you=bian,maxx=x,maxy=y;}dp[u][i].x[0]=maxx;dp[u][i].x[1]=maxy;}}}inline ll work(){ans=-inf;sort(a+1,a+s+1);for(int i=1;i<=s;++i){vis[a[i].x]=a[i].tag;val[a[i].x]=a[i].y+dis[a[i].x];}int start=1;st[top=1]=rbs[rbs[0]=1]=1;if(a[1].x==1)start++;for(int i=start;i<=s;++i){int x=a[i].x,lc=getlca(x,st[top]);if(lc==st[top]){st[++top]=x;rbs[++rbs[0]]=x;continue;}while(top>1){int xx=st[top],yy=st[top-1];if(dfn[yy]<=dfn[lc]){vec[lc].push_back(xx);top--;break;}vec[yy].push_back(xx);top--;} if(st[top]!=lc){st[++top]=lc;rbs[++rbs[0]]=lc;}if(st[top]!=x){st[++top]=x;rbs[++rbs[0]]=x;}}while(top>1){vec[st[top-1]].push_back(st[top]);top--;}ddp(1);while(rbs[0]){int x=rbs[rbs[0]];vis[x]=0;val[x]=0;vec[x].clear();dp[x][1].clear();dp[x][2].clear();rbs[0]--;}s=0;return ans;} } namespace T1{int head[N<<1],tot,num,size[N<<1],sum,nowroot,root,ga;bool jin[N<<2];ll deep[N<<1],ans;struct edge{int n,to;ll l;}e[N<<2];vector<int>vec[N];vector<ll>val[N];inline void add(int u,int v,ll l){vec[u].push_back(v);val[u].push_back(l);}vector<int>::iterator it;inline void add2(int u,int v,ll l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=l;}void dfs(int u,int fa){int now=0;for(int i=0;i<vec[u].size();++i){int v=vec[u][i];ll va=val[u][i];if(v==fa)continue;dfs(v,u);if(!now){add2(u,v,va);now=u;}else{++num;add2(now,num,0);add2(num,v,va);now=num;}}}void getroot(int u,int fa){size[u]=1;for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!jin[i]){int v=e[i].to;getroot(v,u);size[u]+=size[v];if(max(size[v],sum-size[v])<nowroot){nowroot=max(size[v],sum-size[v]);root=i;ga=size[v];}}}void getdeep(int u,int fa,int tag){if(u<=n)a[++s]=node{tag,u,deep[u]};for(int i=head[u];i;i=e[i].n)if(!jin[i]&&e[i].to!=fa){int v=e[i].to;deep[v]=deep[u]+e[i].l;getdeep(v,u,tag);}}void solve(int now,int sm){if(sm==1)return;root=tot+1;nowroot=2e9;sum=sm;getroot(now,0);jin[root]=jin[root^1]=1;int x=e[root].to,y=e[root^1].to,sumx=ga,sumy=sm-ga;deep[x]=0;deep[y]=0;getdeep(x,y,1);getdeep(y,x,2);ans=max(T2::work()+e[root].l,ans);solve(x,sumx);solve(y,sumy);}inline void work(){num=n;tot=1;dfs(1,0);solve(1,num);printf("%lld",ans);} } int main(){n=rd();int u,v;ll w;for(int i=1;i<n;++i){u=rd();v=rd();w=rd();T1::add(u,v,w);T1::add(v,u,w);}for(int i=1;i<n;++i){u=rd();v=rd();w=rd();T2::add(u,v,w);T2::add(v,u,w);}for(int i=1;i<n;++i){u=rd();v=rd();w=rd();T3::add(u,v,w);T3::add(v,u,w); }T3::prework();T2::prework();T1::work();return 0; }

轉載于:https://www.cnblogs.com/ZH-comld/p/10388820.html

總結

以上是生活随笔為你收集整理的[WC2018]通道的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。