网站收录系统,备案时如何关闭网站,做网站策划的工具,wordpress中文版主题题目实际上是求环套树森林中每个环套树的直径。 对于环套树的直径#xff0c;可以先找到这个环套树上面的环。然后把环上的每一点都到达的外向树上的最远距离作为这个点的权值。 那么直径一定就是从环上的某个点开始#xff0c;某个点结束的。 把环拆成链#xff0c;定义dp[… 题目实际上是求环套树森林中每个环套树的直径。 对于环套树的直径可以先找到这个环套树上面的环。然后把环上的每一点都到达的外向树上的最远距离作为这个点的权值。 那么直径一定就是从环上的某个点开始某个点结束的。 把环拆成链定义dp[i]表示第i个点为结束点的最远距离显然有dp[i]val[j]sum[i]-sum[j-1]val[i].显然可以用单调队列优化这个DP。 剩下的就是这样依次统计每个环套树的直径之和。 对于环套树上找环可以借鉴最小树形图找环的技巧。 首先将边定向保证每个点的出度为1.由于环套树的性质这样从这颗树的任意点开始搜索一定会回到原来访问过的点在这个过程中记录好每个点的前驱。 就可以很easy的将这个环找出来。 #include cstdio
#include cstring
#include algorithm
#include stack
#include cctype
#include iostream
#define N 1050000
using namespace std;
inline int getc() { static const int L 115; static char buf[L],*Sbuf,*Tbuf; if(ST){ T(Sbuf)fread(buf,1,L,stdin); if(ST)return EOF; } return *S;
}
inline int getint() { int c; while(!isdigit(c getc())); int tmp c-0; while(isdigit(cgetc())) tmp(tmp1)(tmp3)c-0; return tmp;
}
struct Syndra
{ int u,v,len,next;
}e[N];
struct Fiona
{ int edge,flag1,flag2; long long temp,max1,max2;
}s[N];
int head[N],cnt,n;
int visit[N],next[N],len[N];
int i,j,k;
long long sa[N],pre[N],ans;
void add(int u,int v,int len)
{ cnt; e[cnt].uu; e[cnt].vv; e[cnt].lenlen; e[cnt].nexthead[u]; head[u]cnt;
}
int que[N1];
long long sum[N1],ret;
long long dp(int num)
{ int top,tail; int u,b,star; int et; for(et1;et(num1);et) { sum[et]sum[et-1]pre[(et-1)num?(et-1-num):(et-1)]; } toptail0; /* que[top]0; for(et1;et(num1);et) { while(et-que[top]num)top; uque[top]; retmax(ret,sa[etnum?et-num:et]sa[unum?u-num:u]sum[et]-sum[u]); bque[tail]; que[tail]et; for(startail;startop;bque[star-1]) { if(sum[et]-sum[b]sa[b]sa[et]) { que[star]b; que[--star]et; } else break; } tailstar; } */ que[tail]0; for(et1;et(num1);et) { while(toptailet-que[top]num)top; uque[top]; retmax(ret,sa[etnum?et-num:et]sa[unum?u-num:u]sum[et]-sum[u]); while(toptailsa[etnum?et-num:et]sa[que[tail-1]num?que[tail-1]-num:que[tail-1]]sum[et]-sum[que[tail-1]])--tail; que[tail]et; } return ret;
}
void build()
{ cnt1; memset(head,0,sizeof(head)); memset(visit,0,sizeof(visit)); ngetint(); for(i1;in;i) { next[i]getint(); len[i]getint(); add(next[i],i,len[i]); }
}
stackintsk;
int fa[N];
void dfs(int x)
{ if(s[x].edge0) { sk.pop(); if(s[x].flag2)retmax(ret,s[x].max1s[x].max2); if(visit[x]-1) return ; x sk.top(); { int v,tts[x].edge; ve[tt].v; visit[v]i; s[x].temps[v].max1e[tt].len; if(s[x].max1s[x].temp) { if(s[x].flag1)s[x].max2s[x].max1,s[x].flag21; else s[x].flag11; s[x].max1s[x].temp; } else if(s[x].max2s[x].temp)s[x].max2s[x].temp,s[x].flag21; s[x].edgee[tt].next; } return ; } int v,tts[x].edge; ve[tt].v; if(visit[v]-1) { s[x].edgee[tt].next; return ; } fa[v]x; s[v].edgehead[v]; sk.push(v);
}
long long handle(int x)
{ s[x].edgehead[x]; sk.push(x); while(!sk.empty()) { dfs(sk.top()); } return s[x].max1;
}/*handle(long long)dfs(void)dfs(long long)*/
/*long long dfs(int x)
{ int et,v,flag1,flag2; long long max1,max2; for(max1max20,flag1flag20,ethead[x];et;ete[et].next) { ve[et].v; if(visit[v]-1)continue; tempdfs(v)e[et].len; visit[v]i; if(max1temp) { if(flag1)max2max1,flag21; max1temp; flag11; } else if(max2temp)max2temp,flag21; } if(flag2)retmax(ret,max1max2); return max1;
}*/
int main()
{ int u,v; build(); for(i1;in;i) { if(!visit[i]) { for(ui;!visit[u];unext[u]) { visit[u]i; } if(visit[u]i) { ret0;cnt0; visit[u]-1; for(vnext[u];v!u;vnext[v]) { visit[v]-1; } vu; do{ pre[cnt]len[v]; sa[cnt]handle(v); vnext[v]; }while(v!u); ansdp(cnt); } } } coutans; return 0;
} View Code 转载于:https://www.cnblogs.com/lishiyao/p/6613433.html
