rt,写到一半不会写了，求大佬帮我补全

题目：

【问题描述】

小YY刚学完如何求解树的直径，为了巩固自己对树的理解，小YY画了一颗结点数为N的超级大的树，突然，他想到了老师上课讲的树的直径的问题。

他想知道，如果删去K条边，把树分成K+1个联通块，所有联通块中最长的直径长度最小是多少，此处树的直径长度指树上最长简单路径的长度。

注：为了防止递归过深爆栈，加入编译命令-Wl,--stack=10000000。

【输入格式】

第一行两个整数N、K，分别表示树的大小和删除的边数。

后面N-1行，每行两个数u、v，表示树的一条边。

【输出格式】

一行一个整数，表示所有删去K条边的情况，所有联通块的最长直径的最小值。

【样例输入1】

6 2 1 2 1 3 1 4 2 5 3 6

【样例输出1】

【样例1解释】

删去(1,2)和(1,3)两条边后，剩下的部分均为两个点连在一起，其中最长路径长度均为1。

【数据范围及约定】

对于所有数据，N ≤ 4 × 105，K ≤ N-1。

对于30%的数据，N,K ≤ 30;

对于50%的数据，N,K ≤ 5 × 104;

对于额外10%的数据，N ≤ 4 × 105，K = 0，；

对于额外10%的数据，N ≤ 4 × 105，保证数据为一条链。

对于100%的数据，N ≤ 4 × 105，K ≤ N-1。

Code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,M=N*2;
struct Edge {
    int next,to,w;
} a[M];
int h[N],idx;
int ans;
inline void add(int x,int y,int w) {
    idx++;
    a[idx].to=y;
    a[idx].w=w;
    a[idx].next=h[x];
    h[x]=idx;
}
int n,k,size[N],t[N],d[N],p[N];
void DFS(int x,int prt) {
    size[x]=1;
    int maxn=0;
    for (int i=h[x]; i; i=a[i].next) {
        int y=a[i].to;
        if (y==prt) continue;
        DFS(y,x);
        maxn=max(maxn,size[y]);
        size[x]+=size[y];
    }
    maxn=max(n-size[x],maxn);
    t[x]=maxn;
}
void DFS1(int i,int k,int u)
{
	if(u==n)
	{
		printf("%d",ans);
	}
}
void solve() {
    cin>>n>>k;
    for (int i=1; i<n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y,1);
        add(y,x,1);
    }
    DFS(1,0);
    
}

int main() {
    solve();
    return 0;
}

水题求助

讨论操作

题目：

Code:

回复

相关推荐

水题求助