如何在虚拟机里面做网站,9元包邮网站怎么做,旅游高端网站建设,可视化拖拽网站建设软件文章目录前言解析找环代码练习环套树的直径代码thanks for reading#xff01;前言 环套树者#xff0c;一个环套一棵树也 解析
定义#xff1a;n个点#xff0c;n条边的无向连通图 其实就是树多了一条边#xff0c;连出了一个环 性质#xff1a;如果对环套树进行dfs前言 环套树者一个环套一棵树也 解析
定义n个点n条边的无向连通图 其实就是树多了一条边连出了一个环 性质如果对环套树进行dfs多出的一条非树边一定是一条返祖边 考虑dfs的过程如果它不是返祖边dfs的时候就会直接从这条边过去该边就会成为树边了
找环
如何在环套树上找到非树边 考虑dfs如果出边指向已经被搜过的点那么这条边和它的反向边就是非树边 注意这里dfs的时候不能传来到当前节点的节点fa而是要传来到这个条的边否则在n2的时候会找不到非树边
代码
void find_circle(int x,int pre){vis[x]1;for(int ifi[x];~i;ip[i].nxt){if(i(pre^1)) continue;int top[i].to;if(vis[to]){ei;ux;vto;continue;}find_circle(to,i);}
} 练习
城市环路 骑士 两道很接近的较水的题 解决环套树后就变成没有上司的舞会了
环套树的直径
找出环上的所有点 首先考虑不经过环的路径对每个点跑一遍树形dp求出每个点不包含环上的点的子树的直径 答案首先可以对这些直径取ma尝试作为答案 下面考虑经过环的路径 刚才dp时可以顺便求出连在每个环上点上的最长链len 那么经过环的最长路径就可以表示为 lenilenjdist(i,j)len_ilen_jdist(i,j)lenilenjdist(i,j) 考虑求上面的最大值可以破环成链倍长后用单调队列优化解决
代码
本题调来调去代码有些屎山
#includebits/stdc.h
using namespace std;
const int N1e6100;
#define ll long long
#define I register int
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n;
struct node{int to,nxt,v;
}p[N1];
int fi[N],cnt-1;
void addline(int x,int y,int v){p[cnt](node){y,fi[x],v};fi[x]cnt;
}
ll ans;
int u,v,fa[N],fv[N];
bool vis[N];
int id[N],E-1;
void find_circle(int x,int pre){//printf(x%d fa%d\n,x,fa[x]);vis[x]1;for(int ifi[x];~i;ip[i].nxt){if(i(pre^1)) continue;if(iE||i(E^1)) continue;int top[i].to;if(vis[to]){Ei;ux;vto;continue;}fa[to]x;fv[to]p[i].v;find_circle(to,i);}
}
ll dis[N],d[N];
void dfs(int x,int f){ll mx0,sec0;d[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||id[to]){//printf( fail:x%d to%d\n,x,to);continue;}dfs(to,x);ll nowdis[to]p[i].v;//printf( x%d to%d now%lld\n,x,to,now);if(nowmx) swap(now,mx);if(nowsec) swap(now,sec);d[x]max(d[x],d[to]);}//printf(x%d mx%lld sec%lld\n,x,mx,sec);dis[x]mx;d[x]max(d[x],mxsec);
}
int q[N],st,ed,len;
ll sum[N1];
ll val(int x,int now){now--;
// printf(val:x%d now%d id%d res%lld\n,x,now,id[x],dis[x]max(sum[now]-sum[id[x]-1],sum[len]-(sum[now])sum[id[x]-1]));return dis[x]max(sum[now]-sum[id[x]-1],sum[len]-(sum[now])sum[id[x]-1]);
}
ll a[N1],dd[N1];
void solve(int x){find_circle(x,-2);int uuu;len1;id[uu]1;while(uu!v){len;uufa[uu];id[uu]len;}uuu;ll res0;dfs(u,0);resmax(res,d[u]);while(uu!v){uufa[uu];dfs(uu,0);resmax(res,d[uu]);}for(uuu;1;uufa[uu]){//printf(u%d dis%lld d%lld\n,uu,dis[uu],d[uu]);if(uuv) break;}for(uuu;uu!v;uufa[uu]){a[id[uu]]fv[uu];dd[id[uu]]dis[uu];sum[id[uu]]sum[id[uu]-1]fv[uu];}a[len]p[E].v;sum[len]sum[len-1]p[E].v;dd[len]dis[v];for(int ilen1;i2*len;i){a[i]a[i-len];dd[i]dd[i-len];sum[i]sum[i-1]a[i];}//for(int i1;i2*len;i) printf(i%d a%lld sum%lld dd%lld\n,i,a[i],sum[i],dd[i]);st1,ed1;q[1]1;for(int i2;i2*len;i){//printf(i%d len%d,i,len);while(stedi-q[st]len) st;//printf( i%d st%d res%lld%lld%lld-%lld\n,i,q[st],dd[q[st]],dd[i],sum[i],sum[q[st]]);resmax(res,dd[q[st]]dd[i]sum[i-1]-sum[q[st]-1]);while(steddd[q[ed]]-sum[q[ed]-1]dd[i]-sum[i-1]) ed--;q[ed]i;}ansres;
// printf(x%d res%lld\n\n,x,res);
}
int main(){memset(fi,-1,sizeof(fi));nread();for(int i1;in;i){int xread(),yread();addline(i,x,y);addline(x,i,y);}for(int i1;in;i){if(!vis[i]){solve(i);}}printf(%lld,ans);
}
/*
5
2 1
3 3
1 2
2 5
2 4
*/
thanks for reading
