舟山网站建设公司,企业怎么做自己的网站,无锡seo网站推广,自己的服务器 做网站P4381 [IOI2008]Island
题意#xff1a;
给你一棵基环树森林#xff0c;求出基环树的直径之和.
题解#xff1a;
对于基环树,我们将环看作根,那么直径有两种情况::
1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可;
2.经过环…P4381 [IOI2008]Island
题意
给你一棵基环树森林求出基环树的直径之和.
题解
对于基环树,我们将环看作根,那么直径有两种情况::
1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可;
2.经过环,答案就是i的子树内长度j的子树内长度i和j之间的距离我们预处理出环上每个点到其子树上的最长距离,在预处理一个环上前缀和,ansmax{sondis[i]sondis[j]sumcircle[i]-sumcircle[j]},更新答案即可. sondis[i]记录环上的第i个点到其子树的最远距离; sumcircle[]记录环上距离前缀和; sumcircle[i]-sumcircle[j]即为i和j的距离
代码
#includecstdio
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
const int N1e63;
int to[N1],nex[N1],head[N],w[N1],tt;
int c[N];//记录当前节点属于第几棵基环树;
int dg[N];//记录度数;
int q[N1];//数组模拟队列;
ll d[N];//d[i]记录第i棵树上的直径;
ll f[N];//f[i]记录从i点向儿子方向上所可以走的最长距离;
ll sumcircle[N1];//环上距离前缀和;
ll sondis[N1];//sondis[i]记录环上的第i个点到其子树的最远距离;
int cnt,n;
bool vis[N];//标记当前基环树是否已解决过;
inline void add(int x,int y,int W){to[tt]y,w[tt]W,nex[tt]head[x],head[x]tt;return ;
}
inline void bfs(int p,int t){int l0,r1;q[1]p,c[p]t;//广搜预处理每一个点所属基环树的编号;while(lr){l;int xq[l];for(int ihead[x],v;i;inex[i]){vto[i];if(!c[v]){q[r]v;c[v]t;}}}return ;
}
inline void top_sort(){//拓扑排序求不经过环的直径,从叶子节点向根(环)遍历;int l0,r0;for(int i1;in;i)if(dg[i]1)q[r]i;//将所有度数为1的点先加入队列中(即叶子结点);while(lr){l;int xq[l];for(int ihead[x],v;i;inex[i]){vto[i];if(dg[v]1){//此时v在以环为根的树上是其实是x的父亲;d[c[x]]max(d[c[x]],f[x]f[v]w[i]);//更新当前基环树上的答案;f[v]max(f[v],f[x]w[i]);//更新父节点可以到达的最远节点;if(--dg[v]1)q[r]v;//若当前度数现在变为1,入队;}}}return ;
}
inline void work(int t,int x){int tot0,l,r,vx,u,i;//在拓扑排序后已经将非环上的边遍历完了,环上的边和点均还未遍历,且度数为2,将x看做环上的起点,v看做终点;do{dg[v]1;sondis[tot]f[v];//将当前点度数记为1,防止反向遍历,同时记录第tot号环上节点到子树上的最短距离;for(ihead[v];i;inex[i]){uto[i];if(dg[u]1){//环上的点度数均大于1,所以度数大于1的点即是环上的点;vu;//更新终点;sumcircle[tot1]sumcircle[tot]w[i];//处理环上距离前缀和;break;//保证向一边枚举,所以找到一个点就break;}}}while(i);if(tot2){//特殊处理二元环;int len0;for(ihead[v];i;inex[i]){uto[i];if(ux){lenmax(len,w[i]);//找出两个点之间较大的边; }}d[t]max(d[t],(ll)lenf[x]f[v]);//更新答案;return ;}for(int ihead[v],u;i;inex[i]){uto[i];if(ux){sumcircle[tot1]sumcircle[tot]w[i];//将起点和终点的距离处理出来;break;}}for(i1;itot;i)//断环为链,再复制一遍数组;{sondis[toti]sondis[i];sumcircle[toti]sumcircle[tot1]sumcircle[i];}q[1]1;lr1;for(int i2;itot1;i){while(lri-q[l]tot)l;//将超出环长度的部分弹出;d[t]max(d[t],sondis[q[l]]sondis[i]sumcircle[i]-sumcircle[q[l]]);while(lrsondis[q[r]]sumcircle[i]-sumcircle[q[r]]sondis[i])--r;//将队尾答案不够优秀的部分弹出;q[r]i;//入队;}return ;
}
int main(){cinn;int x,W;for(int i1;in;i){scanf(%d%d,x,W);add(x,i,W);add(i,x,W);dg[x];dg[i];}for(int i1;in;i)if(!c[i])bfs(i,cnt);//预处理;top_sort();//拓扑排序求直径;ll ans0;for(int i1;in;i)if(dg[i]1!vis[c[i]]){//如果当前基环树未被处理,并且当前点是环上点,就处理;vis[c[i]]true;work(c[i],i);ansd[c[i]];//累加答案;}coutans\n;return 0;
}
