网站建设公司业务提成多少,住房和城乡建设部官网政务服务门户,网站 移动app开发,wordpress 示例页面 删除文章目录前言解析找环代码练习环套树的直径代码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
