信息学奥赛-提高级 题库
树上的数
【题目描述】
给定一个大小为n的树,它共有n个结点与n-1条边,结点从1~n编号。初始 时每个结点上都有一个1~n的数字,且每个1~n的数字都只在恰好一个结点上出现。
接下来你需要进行恰好n-1次删边操作,每次操作你需要选一条未被删去的边, 此时这条边所连接的两个结点上的数字将会交换.然后这条边将被删去。
n-1次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字 1~n所在的结点编号依次排列,就得到一个结点编号的排列Pi。现在请你求出,在最 优操作方案下能得到的字典序最小的Pi。

如上图,蓝圈中的数字1〜5 一开始分别在结点②、①、③、⑤、④。按照⑴⑷(3)⑵ 的顺序删去所有边,树变为下图。按数字顺序得到的结点编号排列为 ①③④②⑤,该 排列是所有可能的结果中字典序最小的。

【输入格式】
从文件tree.in中读入数据。
本题输入包含多组测试数据。
第一行一个正整数T,表示数据组数。
对于每组测试数据:
第一行一个整数n,表示树的大小。
第二行n个整数,第i (1≤i≤ n)个整数表示数字i初始时所在的结点编号。 接下来n-1行每行两个整数x,y,表示一条连接x号结点与y号结点的边。
【输出格式】
输出到文件tree.out中。
对于每组测试数据,输出一行共n个用空格隔开的整数,表示最优操作方案下所 能得到的字典序最小的Pi。
【样例1输入】
4
5
2 1 3 5 4
1 3
1 4
2 4
4 5
5
3 4 2 1 5
1 2
2 3
3 4
4 5
5
1 2 5 3 4
1 2
1 3
1 4
1 5
10
1 2 3 4 5 7 8 9 10 6
1 2
1 3
1 4
1 5
5 6
6 7
7 8
8 9
9 10
【样例1输出】
1 3 4 2 5
1 3 5 2 4
2 3 1 4 5
2 3 4 5 6 1 7 8 9 10
【数据范围】

对于所有测试点:1 ≤ T ≤ 10,保证给出的是一个树。
#include<cstdio>
#include<vector>
using namespace std;
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
// #define FILEOI
#define cg (c=getchar())
template<class T>inline void qread(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
inline int qread(){
int x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=-1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);putchar(x%10^48);
}
const int MAXN=2000;
struct edge{
int to,nxt;
edge(){}
edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,siz[MAXN+5];
inline void add_edge(const int u,const int v){
++siz[u],++siz[v];
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
}
int N,minp;
int pt[MAXN+5];
int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];
//这条边的 前驱,后继
int rt[MAXN+5][MAXN+5][2];
//点 u 的某一条边的 前根节点、后根节点
int len[MAXN+5][MAXN+5];
//这条边 所在链 的链表长度
inline void init(){
qread(N);
ecnt=0;
rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;
rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;
int u,v;
rep(i,1,N-1){
qread(u,v);
add_edge(u,v);
pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;
rt[u][v][0]=rt[u][v][1]=v;
rt[v][u][0]=rt[v][u][1]=u;
len[u][v]=len[v][u]=1;
}
}
void findPath(const int u,const int p){//当前节点、前一个节点
int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
//a:来的边的前根 ; b:来的边的后根
if(p==N+1){//这是起点
for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(ta!=v || (pre[u][p]==tb && len[u][ta]<siz[u]))
//条件一:如果这条边已经有一个起点且不是自己
//条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来
continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起
findPath(v,u);//否则可行
}
}
else{
if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面
if(pre[u][N+1]==0 && (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:
//如果这个点的末删边还没有被指定(必须满足)
//并且:
//1.如果这条链接上开头,那么如果必须满足所有的边都在这条链上
//2.如果没有接上开头,那么长度随意
minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点
for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边,与其尾相连
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况
//如果这两条边已经在同一条链上
//或者这个边不是一个起始边, 即枚举边的前面还有东西
//或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边
continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上
if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])
//如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头
//那么它们组合起来必须等于所有边的数量之和
//否则, 这就是 提前自闭 的情况
continue;
findPath(v,u);//如果以上都不满足, 那么这条边是合法的
}
}
else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边
}
}
inline void merge(const int u,const int a,const int b){
//函数条件:以 a 所在的链表为前链表
//并且满足 a 是前链表尾, b 是后链表头
int ta=rt[u][a][0],tb=rt[u][b][1];
nxt[u][a]=b;
pre[u][b]=a;
for(int i=ta;i && i!=N+1;i=nxt[u][i]){
//访问链表的基本操作
//更新每个点的前根、后根
rt[u][i][0]=ta;
rt[u][i][1]=tb;
}
len[u][ta]+=len[u][b];
}
bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记
//如果这条路径找到终点, 返回 1, 否则返回 0
if(u==minp){//如果找到了终点
pre[u][N+1]=p;//把这条边设为最后删除的边
nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的
return 1;
}
int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
if(p==N+1){//这是起飞点
for(int i=tail[u],v;i;i=e[i].nxt){
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(ta!=v || (pre[u][N+1]==tb && len[u][ta]<siz[u]))
//如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了
//或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面
continue;//那么这条边肯定不在路径上面, 可直接跳过
if(getMark(v,u)){//如果这就是正确的路径
nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边
pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)
return 1;
}
}
}
else{//如果点 u 是中转点, 那么考虑枚举中转边
if(p==b){//如果这条边在链上后面没有其他边的时候
for(int i=tail[u],v;i;i=e[i].nxt){
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释
continue;
if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])//同样参考 findPath() 中同样位置
continue;
if(getMark(v,u)){
merge(u,p,v);//把链表合并为一个
return 1;
}
}
}
else getMark(nxt[u][p],u);
}
return 0;
}
signed main(){
#ifdef FILEOI
freopen("rdata.out","r",stdin);
freopen("file.out","w",stdout);
#endif
int T=qread();
while(T--){
init();
if(N==1){
writc(1,'\n');
continue;
}
rep(i,1,N){
minp=N+1;
findPath(pt[i],N+1);
// printf("%d\n",minp);
getMark(pt[i],N+1);
writc(minp,' ');
}
putchar('\n');
}
return 0;
}
树的重心
小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:
1.一个大小为n的树由n个结点与n-1条无向边构成,且满足任意两个结点间有 且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个 子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树 中删去c及与它关联的边后,分裂出的所有子树的大小均不超过
(其中Lx」 是下取整函数)。对于包含至少一个结点的树.它的重心只可能有1或2个。
课后老师给出了一个大小为n的树S,树中结点从1~n编号。小简单的课后作业 是求出S单独删去每条边后,分裂出的两个子树的重心编号和之和。即:

上式中,E表示树S的边集,(u,n)表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边(u,v)后,u号点与V号点所在的被分裂出的子树。
小简单觉得作业并不简单,只好向你求助,请你教教他。
【输入格式】
从文件centroid.in中读入数据。
本题输入包含多组测试数据。
第一行一个整数T表示数据组数。
接下来依次给岀每组输入数据,对于每组数据:
第一行一个整数n表示树S的大小。
接下来n -1行,每行两个以空格分隔的整数 ui,vi,表示树中的一条边(ui,vi)。
【输出格式】
输出到文件centroid.out中。
共T行,每行一个整数.第i行的整数表示:第i组数据给岀的树单独删去每条边 后,分裂出的两个子树的重心编号和之和。
【样例1输入】
2
5
12
23
24
35
7
1 2
1 3
1 4
3 5
3 6
6 7
【样例1输出】
32
56
【样例1解释】
对于第一组数据:
删去边(1,2), 1号点所在子树重心编号为{1}, 2号点所在子树重心编号为{2,3}。 删去边(2,3), 2号点所在子树重心编号为⑵,3号点所在子树重心编号为{3,5}。
删去边(2,4), 2号点所在子树重心编号为{2,3}, 4号点所在子树重心编号为{4}。 删去边(3,5), 3号点所在子树重心编号为{2}, 5号点所在子树重心编号为{5}。
因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。
【数据范围】

表中特殊性质一栏,两个变量的含义为存在一个1~n的排列
使得:
A:树的形态是一条链。即
存在一条边(pi,pi+1)。
B:树的形态是一个完美二叉树。即
存在两条边(Pi,P2i)与(Pi,P2i+1)。 对于所有测试点:
保证给岀的图是一个树。
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn = 300000;
const int Maxlog = 19;
typedef long long ll;
#ifdef LOACL
bool ___;
#endif
struct Edge {
int to;
Edge *nxt;
};
Edge pool[Maxn * 2 + 5];
Edge *G[Maxn + 5], *ecnt;
inline void addedge(int u, int v) {
Edge *p = ++ecnt;
p->to = v, p->nxt = G[u];
G[u] = p;
}
int N;
int siz[Maxn + 5];
int mxson[Maxn + 5], mx2son[Maxn + 5];
ll ans;
int s[Maxn + 1][Maxlog + 2];
int f[Maxn + 5];
inline void clear() {
for(int i = 1; i <= N; i++)
mxson[i] = mx2son[i] = 0;
for(int i = 1; i <= N; i++)
for(int j = 0; j <= Maxlog; j++)
s[i][j] = 0;
for(int i = 1; i <= N; i++)
G[i] = NULL;
ecnt = &pool[0];
ans = 0;
}
inline void modify(int u) {
for(int i = 1; i <= Maxlog; i++)
s[u][i] = s[s[u][i - 1]][i - 1];
}
void PreDFS(int u, int fa) {
siz[u] = 1, f[u] = fa;
for(Edge *p = G[u]; p != NULL; p = p->nxt) {
int v = p->to;
if(v == fa) continue;
PreDFS(v, u);
siz[u] += siz[v];
if(siz[v] > siz[mxson[u]]) {
mx2son[u] = mxson[u];
mxson[u] = v;
} else if(siz[v] > siz[mx2son[u]])
mx2son[u] = v;
}
s[u][0] = mxson[u];
modify(u);
}
inline void calc(int u) {
int tot = siz[u], rt = u;
for(int i = Maxlog; i >= 0; i--)
if(tot - siz[s[u][i]] <= tot / 2)
u = s[u][i];
if(siz[s[u][0]] <= tot / 2) ans += u;
if(u != rt && siz[u] <= tot / 2) ans += f[u];
}
void DFS(int u, int fa) {
if(fa != 0) calc(fa), calc(u);
int flag = 0, t1;
if(N - siz[u] > siz[mxson[u]]) {
t1 = mx2son[u], flag = 1;
mx2son[u] = mxson[u], mxson[u] = fa;
} else if(N - siz[u] > siz[mx2son[u]]){
t1 = mx2son[u], flag = 2;
mx2son[u] = fa;
}
for(Edge *p = G[u]; p != NULL; p = p->nxt) {
int v = p->to;
if(v == fa) continue;
siz[u] += siz[fa] - siz[v], f[u] = v;
if(v == mxson[u]) s[u][0] = mx2son[u];
else s[u][0] = mxson[u];
modify(u);
DFS(v, u);
siz[u] -= siz[fa] - siz[v], f[u] = fa;
}
if(flag == 1) {
mxson[u] = mx2son[u], mx2son[u] = t1;
} else if(flag == 2) mx2son[u] = t1;
s[u][0] = mxson[u];
modify(u);
}
#ifdef LOACL
bool ____;
#endif
int main() {
#ifdef LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int _;
scanf("%d", &_);
while(_--) {
scanf("%d", &N);
clear();
for(int i = 1; i < N; i++) {
int u, v;
scanf("%d %d", &u, &v);
addedge(u, v), addedge(v, u);
}
PreDFS(1, 0);
DFS(1, 0);
printf("%lld\n", ans);
}
#ifdef LOACL
printf("%.2f\n", (&____ - &___) / 1048576.0);
#endif
return 0;
}
保卫王国
【问题描述】
Z 国有n座城市,n − 1条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。
Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:
一座城市可以驻扎一支军队,也可以不驻扎军队。
由道路直接连接的两座城市中至少要有一座城市驻扎军队。
在城市里驻扎军队会产生花费,在编号为i的城市中驻扎军队的花费是pi。
小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了m个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第j个要求能够满足上述驻扎条件(不需要考虑第 j 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第j个要求无法满足,则需要输出-1 (1 ≤ j ≤ m)。现在请你来帮助小 Z。
【输入格式】
输入文件名为 defense.in。
第 1 行包含两个正整数n, m和一个字符串type,分别表示城市数、要求数和数据类型。type是一个由大写字母 A,B 或 C 和一个数字 1,2,3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。
第2行n个整数pi,表示编号i的城市中驻扎军队的花费。
接下来n − 1行,每行两个正整数u, v,表示有一条u到v的双向道路。
接下来m行,第j行四个整数a, x, b, y(a ≠ b),表示第j个要求是在城市a驻扎x支军队,在城市b驻扎y支军队。其中,x 、 y 的取值只有 0 或 1:若 x 为 0,表示城市 a 不得驻扎军队,若 x 为 1,表示城市 a 必须驻扎军队;若 y 为 0,表示城市 b 不得驻扎军队,若 y 为 1,表示城市 b 必须驻扎军队。
输入文件中每一行相邻的两个数据之间均用一个空格分隔。
【输出格式】
输出文件名为 defense.out。
输出共m行,每行包含 1 个整数,第j行表示在满足国王第j个要求时的最小开销,如果无法满足国王的第j个要求,则该行输出-1。
【输入输出样例 1】

【样例解释】
对于第一个要求,在 4 号和 5 号城市驻扎军队时开销最小。
对于第二个要求,在 1 号、2 号、3 号城市驻扎军队时开销最小。
第三个要求是无法满足的,因为在 1 号、5 号城市都不驻扎军队就意味着由道路直接连
接的两座城市中都没有驻扎军队。
【数据规模与约定】
对于 100%的数据,n, m ≤ 300000,1 ≤ pi ≤ 100000。

数据类型的含义:
A:城市i与城市i + 1直接相连。
B:任意城市与城市 1 的距离不超过 100(距离定义为最短路径上边的数量),即如果这棵树以 1 号城市为根,深度不超过 100。
C:在树的形态上无特殊约束。
1:询问时保证a = 1, x = 1,即要求在城市 1 驻军。对b, y没有限制。
2:询问时保证a, b是相邻的(由一条道路直接连通)
3:在询问上无特殊约束。
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 100005
#define MAXM MAXN*2
#define ll long long
#define reg register ll
#define INF 1000000000000000007ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define rep(i,a) for (reg i=last[a];i;i=next[i])
#define O3 __attribute__((optimize("-O3")))
ll last[MAXM],next[MAXM],tov[MAXM];
ll p[MAXN],depth[MAXN],fa[MAXN];
ll f[MAXN][2],g[MAXN][2];
ll anc[MAXN][21];
ll n,m,tot,ans;
char type[5];
struct node
{
ll a[2][2];
}dis[MAXN][21],A,B,C;
O3 inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
O3 inline ll min(ll x,ll y)
{
return x<y?x:y;
}
O3 inline void swap(ll &x,ll &y)
{
x=x+y,y=x-y,x=x-y;
}
O3 inline void link(ll x,ll y)
{
next[++tot]=last[x],last[x]=tot,tov[tot]=y;
}
O3 inline void dfs1(ll x)
{
depth[x]=depth[fa[x]]+1,anc[x][0]=fa[x];
fo(i,1,20)anc[x][i]=anc[anc[x][i-1]][i-1];
f[x][0]=0,f[x][1]=p[x];
rep(i,x)if (tov[i]!=fa[x])
{
fa[tov[i]]=x,dfs1(tov[i]);
f[x][0]+=f[tov[i]][1];
f[x][1]+=min(f[tov[i]][0],f[tov[i]][1]);
}
}
O3 inline void dfs2(ll x)
{
if (x==1)g[x][0]=f[x][0],g[x][1]=f[x][1];
else
{
g[x][0]=f[x][0]+g[fa[x]][1]-min(f[x][0],f[x][1]);
g[x][1]=f[x][1]+min(g[fa[x]][0]-f[x][1],g[fa[x]][1]-min(f[x][0],f[x][1]));
}
rep(i,x)if (tov[i]!=fa[x])
{
dis[tov[i]][0].a[0][0]=INF;
dis[tov[i]][0].a[1][0]=f[x][0]-f[tov[i]][1];
dis[tov[i]][0].a[0][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);
dis[tov[i]][0].a[1][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);
dfs2(tov[i]);
}
}
O3 inline node merge(node A,node B)
{
memset(C.a,60,sizeof(C.a));
fo(i,0,1)fo(j,0,1)fo(k,0,1)
C.a[i][j]=min(C.a[i][j],A.a[i][k]+B.a[k][j]);
return C;
}
O3 int main()
{
freopen("defense.in","r",stdin);
freopen("defense.out","w",stdout);
//freopen("readin.txt","r",stdin);
n=read(),m=read(),scanf("%s",&type);
fo(i,1,n)p[i]=read();
fo(i,1,n-1)
{
ll x=read(),y=read();
link(x,y),link(y,x);
}
dfs1(1),dfs2(1);
fo(j,1,20)fo(i,1,n)dis[i][j]=merge(dis[i][j-1],dis[anc[i][j-1]][j-1]);
while (m--)
{
ll a=read(),x=read(),b=read(),y=read();
if (x+y==0 && ((fa[a]==b) || (fa[b]==a)))
{
printf("-1\n");
continue;
}
if (depth[a]<depth[b])swap(a,b),swap(x,y);
memset(A.a,60,sizeof(A.a));
memset(B.a,60,sizeof(B.a));
A.a[x][x]=f[a][x],B.a[y][y]=f[b][y];
fd(i,20,0)if (depth[anc[a][i]]>depth[b])
{
A=merge(A,dis[a][i]),a=anc[a][i];
}
if (fa[a]==b)
{
printf("%lld\n",y==0?g[b][0]-f[a][1]+A.a[x][1]:
g[b][1]-min(f[a][0],f[a][1])+min(A.a[x][0],A.a[x][1]));
continue;
}
if (depth[a]!=depth[b])A=merge(A,dis[a][0]),a=fa[a];
fd(i,20,0)if (anc[a][i]!=anc[b][i])
{
A=merge(A,dis[a][i]),B=merge(B,dis[b][i]);
a=anc[a][i],b=anc[b][i];
}
printf("%lld\n",min(g[fa[a]][0]-f[a][1]-f[b][1]+A.a[x][1]+B.a[y][1],
g[fa[a]][1]-min(f[a][0],f[a][1])-min(f[b][0],f[b][1])+min(A.a[x][0],A.a[x][1])+min(B.a[y][0],B.a[y][1])));
}
return 0;
}
2-3 树是一种特殊的树,它满足两个条件:
(1)每个内部结点有两个或三个子结点;
(2)所有的叶结点到根的路径长度相同。
如果一棵 2-3 树有 10 个叶结点,那么它可能有( )个非叶结点。
宝藏
【问题描述】
参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 n 个深埋在地下的宝藏屋,也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。
在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是:
这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋)。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代价最小,并输出这个最小值。
【输入格式】
输入文件名为 treasure.in。
第一行两个用空格分离的正整数 n 和 m,代表宝藏屋的个数和道路数。
接下来 m 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏屋的编号(编号为 1~n),和这条道路的长度 v。
【输出格式】
输出文件名为 treasure.out。
输出共一行,一个正整数,表示最小的总代价。
【输入输出样例 1】

【输入输出样例 1 说明】


【样例输入输出 2】

【输入输出样例 2 说明】

【数据规模与约定】
对于 20%的数据:
保证输入是一棵树,1≤n≤8,v≤5000 且所有的 v 都相等。
对于 40%的数据:
1≤n≤8,0≤m≤1000,v≤5000 且所有的 v 都相等。
对于 70%的数据:
1≤n≤8,0≤m≤1000,v≤ 5000
对于 100%的数据:
1≤n≤12,0≤m≤1000,v≤ 500000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,tot,ans;
int mapp[110][110],dis[110][110],Log[4100];
int f[15][4100],g[4100],ref[4100],v[15],p[15];
int main(){
//freopen("treasure.in","r",stdin);
//freopen("treasure.out","w",stdout);
scanf("%d%d",&n,&m);
register int i,j,a,b,c,x;
for(i=0;i<n;i++) for(j=0;j<n;j++) mapp[i][j]=60000000;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c),a--,b--;
mapp[a][b]=mapp[b][a]=min(mapp[a][b],c);
}//建图
for(i=0;i<n;i++) Log[1<<i]=i;
memset(f,0x3f,sizeof(f));
for(i=0;i<n;i++) f[0][1<<i]=0;
for(i=0;i<n;i++) //开始DP
for(x=0;x<(1<<n);x++){
tot=0;
for(a=0;a<n;a++)
if(!(x&(1<<a))){
v[tot]=60000000,p[tot]=1<<a;
for(j=x;j;j-=j&-j){
b=Log[j&-j];
v[tot]=min(v[tot],mapp[a][b]*(i+1));//计算代价
}
tot++;
}
for(j=1;j<(1<<tot);j++){
g[j]=g[j-(j&-j)]+v[Log[j&-j]];//每个点与x中的某个点连通所需要的最小代价。
ref[j]=ref[j-(j&-j)]|p[Log[j&-j]];//枚举子集
f[i+1][x|ref[j]]=min(f[i+1][x|ref[j]],f[i][x]+g[j]);
}
}
ans=1<<30;
for(i=0;i<=n;i++) ans=min(ans,f[i][(1<<n)-1]);//最优状态从走到每一个点但最深深度不同的状态中取
printf("%d",ans);
return 0;
}
子串
【问题描述】
有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出的位置不同也认为是不同的方案。
【输入格式】
输入文件名为 substring.in。
第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问题描述中所提到的 k,每两个整数之间用一个空格隔开。
第二行包含一个长度为 n 的字符串,表示字符串 A。
第三行包含一个长度为 m 的字符串,表示字符串 B。
【输出格式】
输出文件名为 substring.out。
输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,007 取模的结果。
【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【输入输出样例说明】
所有合法方案如下:(加下划线的部分表示取出的子串)
样例 1:aab aab / aab aab
样例 2:a ab aab / a aba ab / a a ba ab / aab a abaa b aab / aa baa b / aab aa b
样例 3:a a b aab / a a baa b / a ab a a b / a aba a ba a b a a b / a a ba a b / aab a a b
【数据规模与约定】
对于第 1 组数据:1≤n≤500,1≤m≤50,k=1;
对于第 2 组至第 3 组数据:1≤n≤500,1≤m≤50,k=2;
对于第 4 组至第 5 组数据:1≤n≤500,1≤m≤50,k=m;
对于第 1 组至第 7 组数据:1≤n≤500,1≤m≤50,1≤k≤m;
对于第 1 组至第 9 组数据:1≤n≤1000,1≤m≤100,1≤k≤m;
对于所有 10 组数据:1≤n≤1000,1≤m≤200,1≤k≤m。
#include<iostream>
#include<cstring>
#define N 1003
#define M 203
#define mod 1000000007
using namespace std;
int dp[3][N][M]={0};
char A[N],B[M];
int n=0,m=0,K=0;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>K;
cin>>(A+1);cin>>(B+1);
for(int i=0;i<=n;i++) dp[0][i][0]=1;
for(int k=1;k<=K;k++){
memset(dp[k&1],0,sizeof(dp[k&1]));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j>i) break;
dp[k&1][i][j]+=dp[k&1][i-1][j];
dp[k&1][i][j]%=mod;
if(A[i]==B[j]){
dp[k&1][i][j]+=(dp[(k-1)&1][i-1][j-1]+dp[k&1][i-1][j-1])%mod;
dp[k&1][i][j]%=mod;
if(i>1) dp[k&1][i][j]-=dp[k&1][i-2][j-1];
dp[k&1][i][j]%=mod;
dp[k&1][i][j]+=mod;
dp[k&1][i][j]%=mod;
}
dp[k&1][i][j]%=mod;
}
}
}
cout<<dp[K&1][n][m]<<endl;
return 0;
}
疫情控制
【问题描述】
H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
【输入】
输入文件名为 blockade.in。
第一行一个整数 n,表示城市个数。
接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。
接下来一行一个整数 m,表示军队个数。
接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。
【输出】
输出文件为 blockade.out。
共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
【输入输出样例】

【输入输出样例说明】
第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间为 3 个小时。
【数据范围】
保证军队不会驻扎在首都。

#include <bits/stdc++.h>
using namespace std;
const int Max=50005;
int n,m,size,l,r,mid,tot1,tot2;
int first[Max],num[Max],f[Max][18],d[Max][18],p[Max],vis[Max];
struct bian{int to,next,len;};
bian edge[Max<<1];
struct shu{int id,len;};
shu a[Max],b[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void build(int x,int y,int z)
{
edge[++size].next=first[x];
first[x]=size;
edge[size].to=y,edge[size].len=z;
}
inline void dfs(int point,int fa)
{
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa) continue;
f[to][0]=point,d[to][0]=edge[u].len;
dfs(to,point);
}
}
inline void pre()
{
for(int j=1;j<=16;j++)
for(int i=1;i<=n;i++)
if(f[i][j-1]) f[i][j]=f[f[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[f[i][j-1]][j-1];
}
inline void search(int point,int fa)
{
if(vis[point]) return;
vis[point]=1;int tag=0;
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa) continue;
tag=1;
search(to,point);
vis[point]&=vis[to];
}
if(!tag) vis[point]=0; //叶子节点需特判
}
inline bool comp(const shu &a,const shu &b){return a.len<b.len;}
inline bool check(int mid)
{
tot1=tot2=0;
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=m;i++)
{
int sum=0,x=p[i];
for(int k=16;k>=0;k--)
if(f[x][k]>1&&sum+d[x][k]<=mid) sum+=d[x][k],x=f[x][k];
if(f[x][0]==1&&sum+d[x][0]<=mid) a[++tot1].len=mid-sum-d[x][0],a[tot1].id=x;
else vis[x]=1;
}
search(1,0);
if(vis[1]) return 1;
for(int u=first[1];u;u=edge[u].next)
if(!vis[edge[u].to]) b[++tot2].len=edge[u].len,b[tot2].id=edge[u].to;
sort(a+1,a+tot1+1,comp),sort(b+1,b+tot2+1,comp);
if(tot1<tot2) return 0;
int tag=1;
for(int i=1;i<=tot1;i++)
{
if(!vis[a[i].id]) vis[a[i].id]=1; //题解中的优先覆盖
else if(a[i].len>=b[tag].len) vis[b[tag].id]=1;
while(tag<=tot2&&vis[b[tag].id]) tag++;
if(tag>tot2) return 1;
}
return tag>tot2;
}
int main()
{
n=get_int();
for(int i=1;i<n;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y,z),build(y,x,z);
}
m=get_int();
for(int i=1;i<=m;i++) p[i]=get_int();
dfs(1,0);
pre();
l=0,r=1e9;int tag=0;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) tag=1,r=mid;
else l=mid+1;
}
if(tag) cout<<r<<"\n";
else cout<<"-1\n";
return 0;
}
树网的核
【问题描述】
设 T=(V, E, W) 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称 T 为树网(treenetwork),其中 V, E 分别表示结点与边的集合,W 表示各边长度的集合,并设 T 有 n 个结点。
路径:树网中任何两结点 a,b 都存在唯一的一条简单路径,用 d(a,b)表示以 a,b 为端点的路径的长度,它是该路径上各边长度之和。我们称 d(a,b)为 a,b 两结点间的距离。一点 v 到一条路径 P 的距离为该点与 P 上的最近的结点的距离:
d(v,P)=min{d(v,u),u 为路径 P 上的结点}。
树网的直径:树网中最长的路径称为树网的直径。对于给定的树网 T,直径不一定是唯一的,但可以证明:各直径的中点(不一定恰好是某个结点,可能在某条边的内部)是唯一的,我们称该
点为树网的中心。
偏心距 ECC(F):树网 T 中距路径 F 最远的结点到路径 F 的距离,即

任务:对于给定的树网 T=(V, E,W)和非负整数 s,求一个路径 F,它是某直径上的一段路径(该路径两端均为树网中的结点),其长度不超过 s(可以等于 s),使偏心距 ECC(F)最小。我们称这个路径为树网 T=(V,E,W)的核(Core)。必要时,F 可以退化为某个结点。一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。
下面的图给出了树网的一个实例。图中,A-B 与 A-C 是两条直径,长度均为 20。点 W 是树网的中心,EF 边的长度为 5。如果指定 s=11,则树网的核为路径 DEFG(也可以取为路径 DEF),偏心距为 8。如果指定 s=0(或 s=1、s=2),则树网的核为结点 F,偏心距为 12。

【输入】
输入文件 core.in 包含 n 行:
第 1 行,两个正整数 n 和 s,中间用一个空格隔开。其中 n 为树网结点的个数,s 为树网的核的长度的上界。设结点编号依次为 1, 2, ..., n。
从第 2 行到第 n 行,每行给出 3 个用空格隔开的正整数,依次表示每一条边的两个端点编号和长度。例如,“2 4 7”表示连接结点 2 与 4 的边的长度为 7。
所给的数据都是正确的,不必检验。
【输出】
输出文件 core.out 只有一个非负整数,为指定意义下的最小偏心距。
【输入输出样例 1】

【输入输出样例 2】

【限制】
40%的数据满足:5<=n<=15
70%的数据满足:5<=n<=80
100%的数据满足:5<=n<=300, 0<=s<=1000。边长度为不超过 1000 的正整数
#include<cstdio>
#include<algorithm>
#include<cstring>
const int inf=0x3f3f3f3f;
using namespace std;
int n,s,a,b,c,maxx=0,mxi,mxj;
int dis[305][305];
int read(){
int ans=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
ans=ans*10+c-48;
c=getchar();
}
return ans*f;
}
int main(){
n=read();s=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)dis[i][j]=inf;
for(int i=1;i<=n-1;i++){
a=read();b=read();c=read();dis[a][b]=dis[b][a]=c;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(dis[i][k]>=inf||dis[k][j]>=inf)continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
if(dis[i][j]>maxx){
maxx=dis[i][j];
mxi=i;mxj=j;
}
}
int ans=inf;
for(int i=1;i<=n;i++){
if(dis[mxi][i]+dis[i][mxj]!=dis[mxi][mxj])continue;
for(int j=1;j<=n;j++){
if(dis[mxi][j]+dis[j][mxj]!=dis[mxi][mxj]||dis[i][j]>s)continue;
int ecc=0;
ecc=max(min(dis[mxi][i],dis[mxi][j]),min(dis[mxj][i],dis[mxj][j]));
ans=min(ans,ecc);
}
}
printf("%d",ans);
return 0;
}