第一题第二题鉴上我前几篇博客poj1985 poj1849：https://www.cnblogs.com/Tyouchie/p/10384379.html
第三题：数的重心；poj1655
来自sjh大佬的版子，邻接表写法
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
const int maxn=2e4+;
template<typename T>inline void read(T &x)
{
x=;
T f=,ch=getchar();
while (!isdigit(ch) && ch^'-') f=-, ch=getchar();
if (ch=='-') f=-, ch=getchar();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
x*=f;
}
int vis[maxn],siz[maxn],ans,pos,n;
int ver[maxn<<],Next[maxn<<],head[maxn],len;
inline void add(int x,int y)
{
ver[++len]=y,Next[len]=head[x],head[x]=len;
}
inline void dfs(int x)
{
vis[x]=,siz[x]=;
int maxpart=;
for (int i=head[x];i;i=Next[i])
{
int y=ver[i];
if (!vis[y])
{
dfs(y);
siz[x]+=siz[y];
maxpart=max(maxpart,siz[y]);
}
}
maxpart=max(maxpart,n-siz[x]);
if (maxpart<ans || (maxpart==ans && x<pos))
ans=maxpart,pos=x;
}
int main()
{
int t;read(t);
while (t--)
{
read(n);
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));
len=pos=;
ans=0x3f3f3f3f;
for (int x,y,i=;i<n;++i)
{
read(x);read(y);
add(x,y);add(y,x);
}
dfs();
printf("%d %d\n",pos,ans);
}
return ;
}
我写的邻接矩阵
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
const int maxn=2e4+;
const int INF=0x3f3f3f3f;
vector<int>G[maxn];
int son[maxn];
int ans,n,balance,t; void dfs(int v,int fa)
{
son[v]=;
int d=G[v].size();
int pre_balance=;
for (int i=;i<d;i++)
{
int k=G[v][i];
if (k!=fa)
{
dfs(k,v);
son[v]+=son[k];
pre_balance=max(pre_balance,son[k]);
}
}
pre_balance=max(pre_balance,n-son[v]);
if (pre_balance<balance || (pre_balance==balance&&v<ans))
{
ans=v;
balance=pre_balance;
}
}
int main()
{
cin>>t;
while (t--)
{
scanf("%d",&n);
for (int i=;i<=n;++i)
G[i].clear();
for (int i=;i<n;i++)
{
int s,e;
scanf("%d%d",&s,&e);
G[s].push_back(e);
G[e].push_back(s);
}
memset(son,,sizeof(son));
ans=;balance=INF;
dfs(,);
cout<<ans<<' '<<balance<<endl;
}
return ;
}
Noip 2018 旅行；luogu5022
题意：一个n个点，m条边的连通图。可以从任意一个点出发，前往任意 一个相邻的未访问的结点，或沿着上一次来这个点的边返回。需要遍历 每一个点。每经过一个新的结点，就将这个结点写下来。最终可以得到 一个序列。求字典序最小的序列。 n ≤ 5000, m ≤ n。
貌似用栈慢一点，洛谷最后一个点过不了，要用02优化；
但是用栈维护单调性比较方便；
n < m：对于树的情况，显然从1出发，每次从字典序最小的相邻结 点DFS即可。
n = m: 对于有环的情况，由于环只有一个，我们可以将环找出来， 枚举删掉环上的每一条边，然后按树的情况求解即可。 时间复杂度O(n 2 )。
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define R register
using namespace std;
typedef long long ull;
const int maxn = 5e3 + ; inline int read() {
int s = , w = ;
char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -; ch = getchar(); }
while (isdigit(ch)) { s = (s << ) + (s << ) + (ch ^ ); ch = getchar(); }
return s * w;
} inline void write(int x)
{
if(x < ) putchar('-'),x = -x;
if(x > ) write(x / );
putchar(x % + '');
} vector <int> vec[maxn];
int ans[maxn], edge[maxn][], t[maxn], vis[maxn];
int n, m, da, db, tsize = ; inline void dfs(int x) {
t[++tsize] = x; vis[x] = ;
int l = vec[x].size();
for (R int i = ; i < l; ++i) {
int y = vec[x][i];
if (!vis[y] && !((x == da && y == db) || (x == db && y == da))) dfs(y);
}
return ;
} inline void check() {
if (tsize != n) return ;
for (R int i = ; i <= n; ++i) {
if (t[i] != ans[i]) {
if (t[i] > ans[i]) return ;
break;
}
}
for (R int i = ; i <= n; ++i) {
ans[i] = t[i];
}
return ;
} int main() {
memset(ans, 0x3f, sizeof(ans));
n = read(), m = read();
for (R int i = ; i <= m; ++i) {
int a = read(), b = read();
vec[a].push_back(b);
vec[b].push_back(a);
edge[i][] = a;
edge[i][] = b;
}
for (R int i = ; i <= n; ++i) sort(vec[i].begin(), vec[i].end());
if (n > m) {
da = -, db = -;
dfs();
check();
}
else {
for (R int i = ; i <= m; ++i) {
tsize = ;
da = edge[i][];
db = edge[i][];
memset(vis, , sizeof(vis));
dfs();
check();
}
}
for (R int i = ; i <= n; ++i) write(ans[i]), putchar(' ');
return ;
}
第四题：BZOJ 1791
跑一个基环树直径；
来自石神的模板；
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
template<typename T>inline void read(T &x)
{
x=;
T f=,ch=getchar();
while (!isdigit(ch)) ch=getchar();
if (ch=='-') f=-, ch=getchar();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
x*=f;
}
int n,m,t;//t是标识符
int ver[maxn<<],edge[maxn<<],next[maxn<<],head[maxn],tot,du[maxn];
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z,next[tot]=head[x],head[x]=tot,++du[y];
}
int c[maxn];//环上的点
int v[maxn];
int q[maxn<<];
void bfs(int s,int t)
{
int l,r;
q[l=r=]=s;//手写队列维护
c[s]=t;//标记连通块（看每个节点属于哪个基环树）
while (l<=r)
{
for (int i=head[q[l]]; i; i=next[i])
if (!c[ver[i]])
{
q[++r]=ver[i];
c[ver[i]]=t;
}
l++;
}
}
ll f[maxn];//每颗子树的直径
ll d[maxn];//每个节点的子树大小
void topsort()//找环操作顺便处理一种情况（直径不经过环）
{
int l=,r=,x,y;
for (int i=; i<=n; ++i)
if (du[i]==)//无向图度数为1
q[++r]=i;
while (l<=r)
{
for (int i=head[x=q[l]]; i; i=next[i])
if (du[y=ver[i]]>)//度大于1可更新答案
{
d[c[x]]=max(d[c[x]],f[x]+f[y]+edge[i]);//子树内最长链
f[y]=max(f[y],f[x]+edge[i]);//f[x]表示x子树中离x最远的点的距离
if ((--du[y])==)
q[++r]=y;
}
l++;
}
}
ll a[maxn<<];
ll b[maxn<<];
void dp(int t,int x)
{
int m=,i,l=,r,y=x;
do
{
a[++m]=f[y];
du[y]=;
for (i=head[y]; i; i=next[i])
if (du[ver[i]]>)//点在环上
{
y=ver[i];
b[m+]=b[m]+edge[i];//b[i]表示环上x到i的距离
break;
}
} while (i);//此时答案为 f[i]+f[j]+dis[i][j]的最大值，dis[i][j]表示环上i到j的最远距离
if (m==)//跑到环外，需要特判
{
for (i=head[y]; i; i=next[i])
if (ver[i]==x)
l=max(l,edge[i]);
d[t]=max(d[t],f[x]+f[y]+l);
return;
}
for (i=head[y]; i; i=next[i])//连接环的首尾
if (ver[i]==x)
{
b[m+]=b[m]+edge[i];
break;
}
for (i=; i<m; ++i)//由于是环，所以复制一份
{
a[m+i]=a[i];
b[m+i]=b[m+]+b[i];
}
q[l=r=]=;
for (i=; i<*m; ++i)
{
while (l<=r && i-q[l]>=m) ++l;
d[t]=max(d[t],a[i]+a[q[l]]+b[i]-b[q[l]]);
while (l<=r && a[q[r]]+b[i]-b[q[r]]<=a[i]) --r;//单调队列维护
q[++r]=i;
}
}
int main()
{
read(n);
for (int i=; i<=n; ++i)
{
int x,y;
read(x);read(y);
add(i,x,y),add(x,i,y);
}
for (int i=; i<=n; ++i)
if (!c[i])
bfs(i,++t);//统计有多少基环树
topsort();//拓扑找环 memset(v,,sizeof(v));//重新利用v数组，当作基环树是否算过
ll ans=0ll;
for (int i=; i<=n; ++i)
if (du[i]> && !v[c[i]])//每个基环树只跑一遍并且此时i是环上一点
{
v[c[i]]=;
dp(c[i],i);//求基环树的直径
ans+=d[c[i]];
}
printf("%lld\n",ans);
return ;
}
第五题：LUOGU CF 835F
第六题“：BZOJ 1040：
题意：n个点n条边的图，每个点都有点权，要求找到一个点集，点集中的 点相互之间不能有边相连，最大化点集的权值和。 1 ≤ n ≤ 106
如果联通的话，就是一个基环树了，否则为基环树森林。
这道题可 以简单的抽象为：基环树的最大独立集。
如果是一棵树该怎么做？
DP。
f [i][0] =∑max(f [son[i]][0], f [son[i][1])
f [i][1] =∑f [son[i]][0]
在每一棵基环树的环上枚举一条边，记它的两个端点为u和v，然后 删掉这条边做树形dp即可。
从该边的两个端点出发选择：
1 强制不选u，v任意，环的贡献为以u做DP的f [u][0]。
2 强制不选v，u任意，环的贡献为以v做DP的f [v][0]。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5e2;
template<typename T>inline void read(T &x)
{
x=;
T f=,ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-, ch=getchar();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
x*=f;
}
int ver[maxn<<],Next[maxn<<],head[maxn],len;
inline void add(int x,int y)
{
ver[++len]=y,Next[len]=head[x],head[x]=len;
}
int n,power[maxn],hate[maxn],vis[maxn],U,V;
ll f[maxn],g[maxn];
inline void dfs(int x,int fa)//dfs找环
{
vis[x]=;
for (int i=head[x];i;i=Next[i])
{
int y=ver[i];
if (y!=fa)
{
if (!vis[y]) dfs(y,x);
else
{
vis[y]=;
U=x,V=y;
return ;
}
}
}
}
inline void tree_dp(int x,int fa,int rt,int ban)//ban 不选的点
{
vis[x]=;
f[x]=power[x];
g[x]=;
for (int i=head[x];i;i=Next[i])
{
int y=ver[i];
if (x==rt && i==ban) continue;
if (y!=fa && y!=rt)
{
tree_dp(y,x,rt,ban);
f[x]+=g[y];
g[x]+=max(g[y],f[y]);
}
}
}
int main()
{
read(n);
for (int i=,k;i<=n;++i)
{
read(power[i]);read(hate[i]);
add(i,hate[i]),add(hate[i],i);
}
ll ans=;
for (int i=;i<=n;++i)
if (!vis[i])
{
dfs(i,-);
int banu,banv;
for (int i=head[U];i;i=Next[i])
if (ver[i]==V)
{
banu=i;
break;
}
for (int i=head[V];i;i=Next[i])
if (ver[i]==U)
{
banv=i;
break;
}
tree_dp(U,-,U,banu);//断环为链并将断开的两个点强制其中一个点为根且不选，做一次树形DP
ll uans=g[U];
tree_dp(V,-,V,banv);//对另一个点做同样操作
ll vans=g[V];
ans+=max(uans,vans);//取两次结果最大值加入ans
}
printf("%lld\n",ans);
return ;
}