社区讨论
13分然而并不能看出有什么问题 求大佬解救
P3128[USACO15DEC] Max Flow P参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6wxa9f
- 此快照首次捕获于
- 2025/11/20 12:09 4 个月前
- 此快照最后确认于
- 2025/11/20 12:09 4 个月前
CPP
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define MAXN 50007
using namespace std;
int n, k, head[MAXN], num_edge, vis_time[MAXN];
int son[MAXN], father[MAXN], dep[MAXN], size[MAXN], top[MAXN];
struct add
{
int to, next;
}edge[MAXN<<1];
void add_edge(int from, int to)
{
edge[++num_edge].to = to;
edge[num_edge].next = head[from];
head[from] = num_edge;
}
int read()
{
int tt = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c))
{
tt = (tt<<1)+(tt<<3)+(c&15);
c = getchar();
}
return tt;
}
void dfs1(int u, int fa)
{
father[u] = fa;
size[u] = 1;
dep[u] = dep[fa]+1;
for(int i=head[u]; i; i=edge[i].next)
{
int v = edge[i].to;
if(v == fa) continue;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
void dfs2(int u, int topu)
{
top[u] = topu;
if(!son[u]) return;
for(int i=head[u]; i; i=edge[i].next)
{
int v = edge[i].to;
if(v == father[u] || v == son[u]) continue;
dfs2(v, v);
}
}
void dfs3(int u)
{
for(int i=head[u]; i; i=edge[i].next)
{
int v = edge[i].to;
if(v == father[u]) continue;
dfs3(v);
vis_time[u] += vis_time[v];
}
}
int LCA(int x, int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = father[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int main()
{
n = read(), k = read();
for(int i=1; i<=n-1; ++i)
{
int x = read(), y = read();
add_edge(x, y); add_edge(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
for(int i=1; i<=k; ++i)
{
int start = read(), finish = read();
int lca = LCA(start, finish);
vis_time[start]++; vis_time[finish]++;
vis_time[lca]--; vis_time[father[lca]]--;
}
dfs3(1);
int maxx = 0;
for(int i=1; i<=n; ++i) maxx = max(maxx, vis_time[i]);
printf("%d\n", maxx);
return 0;
}
莫名其妙挂掉了
第一个点比标准输出少了一万多
求大佬解救
回复
共 4 条回复,欢迎继续交流。
正在加载回复...