呼和浩特建设厅网站,学做早餐网站,电子商务网站建设策划书模板,温州建站平台题目链接 类似求树的直径#xff0c;可以用(类似)树形DP求每个点其子树(在仙人掌上就是诱导子图)最长链、次长链#xff0c;用每个点子节点不同子树的 max{最长链}max{次长链} 更新答案。(不需要存次长链#xff0c;求解过程中先更新ans#xff0c;然后再更新最长链即可) 设…题目链接 类似求树的直径可以用(类似)树形DP求每个点其子树(在仙人掌上就是诱导子图)最长链、次长链用每个点子节点不同子树的 max{最长链}max{次长链} 更新答案。(不需要存次长链求解过程中先更新ans然后再更新最长链即可) 设f[i]为点i的诱导子图中最长链的长度。 对于环我们找一个环上dep[]最小的点x代表这个环 看做一个点(dep为按DFS顺序更新的)求出f[x]环以外的部分像树一样直接做就可以。 对于环的处理f[x]比较显然f[x]max{f[v]dis(x,v)}v为其环上一点dis(x,v)为x,v在环上的最小距离。 环上如何更新答案把环上所有点都拿出来ansmax{f[u]f[v]dis(u,v)}。 u,v是环上的点按顺序编号dis(u,v)v-u(v-ulen/2)那么ans可以写成 max{f[u]-uf[v]v}。固定v因为u是单增的所以之前最大的f[u]-u在后面也是最大的可以用单调队列维护。 dis()是环上最小距离所以v-u不能超过 环长/2。因为是个环所以把它拆成一个3/2*len的序列更新ans。 之后用f[v]dis(x,v)更新f[x]。 扫一遍所有的环总共复杂度是\(O(m)\)。 总Tarjan对于不在同一环上的点用f[x]f[v]1更新ans再用f[v]更新f[x]对于其它的点像上面那样取出环单调队列处理。 //8760kb 192ms
#include cstdio
#include cctype
#include algorithm
#define gc() getchar()
const int N5e45,MN2;//边数。。大概最多2n条int n,m,Ans,Enum,H[N],to[M],nxt[M],dfn[N],low[N],id,fa[N],dep[N],f[N],q[N],A[N1];inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}
inline void AddEdge(int u,int v){to[Enum]v, nxt[Enum]H[u], H[u]Enum;to[Enum]u, nxt[Enum]H[v], H[v]Enum;
}
void DP(int x,int ed)
{int ndep[ed]-dep[x]1;//lengthfor(int in; i; --i) A[i]f[ed], edfa[ed];int n2n(n1);//能同时更新别的的最多只有n/2个点所以只需要3/2*n for(int in1; in2; i) A[i]A[i-n];int h1,t1; q[1]1;for(int i2; in2; i)//i,q[]是点拿出来的A[]是f[]{while(ht i-q[h](n1)) h;Ansstd::max(Ans,A[q[h]]-q[h]A[i]i);while(ht A[q[t]]-q[t]A[i]-i) --t;//注意这个比较是因为更新队首时不是根据值的大小而是限制条件(竟然有90...) q[t]i;}for(int i2; in; i)f[x]std::max(f[x],A[i]std::min(i-1,n-i1));
}
void DFS(int x)
{dfn[x]low[x]id;for(int v,iH[x]; i; inxt[i])if((vto[i])!fa[x]){if(!dfn[v])fa[v]x, dep[v]dep[x]1, DFS(v), low[x]std::min(low[x],low[v]);if(low[v]dfn[x])//不是环 Ansstd::max(Ans,f[x]f[v]1), f[x]std::max(f[x],f[v]1);low[x]std::min(low[x],dfn[v]);//无向图就不需要什么在栈中了 //只需判环所以和下一行写法一样
// low[x]std::min(low[x],low[v]);}for(int iH[x]; i; inxt[i])if(fa[to[i]]!xdfn[to[i]]dfn[x]) DP(x,to[i]);//找环的另一个端点 //端点是后访问的点而不只是to[i]!fa[x](当x同时在两个环上时)能找到之前的环和x之后的环但x不代表(没必要)之前访问的环这样找环还麻烦。。不是沿to[i]的fa到x。
}int main()
{nread(),mread();int num,u,v;while(m--){numread()-1, uread();while(num--) vread(),AddEdge(u,v),uv;}DFS(1);printf(%d,Ans);return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/8976378.html
