高新网站制作哪家好,seo排名点击器,商务网页设计与制作软件,沈阳在线制作网站给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1#xff0c;其中 0 号点为根节点。最初#xff0c;从根节点可以抵达所有节点#xff08;包括自己#xff09;。如果我们将所有边权小于 X 的边全部删掉#xff0c;那么从根节点可以抵达的节点数目就可能发生改变。 …给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1其中 0 号点为根节点。最初从根节点可以抵达所有节点包括自己。如果我们将所有边权小于 X 的边全部删掉那么从根节点可以抵达的节点数目就可能发生改变。 现在给定一个整数 Y请你找到最小的非负整数 X使得所有边权小于 X 的边都被删掉以后根节点能够抵达的节点数目包括自己不超过 Y。
输入格式 第一行包含整数 T表示共有 T 组测试数据。每组数据第一行包含两个整数 N,Y。 接下来 N−1行每行包含三个整数 U,V,W表示点 U 和点 V 之间存在一条权值为 W 的边。
输出格式 每组数据输出一行一个 X。 注意X 应不小于 0。
数据范围 1≤T≤100, 1≤N≤20000, 1≤Y≤N, 0≤U,VN, 0≤W≤107,
保证在一个测试点中所有 N 的和不超过 105。
输入样例 2 3 2 0 1 2 0 2 3
6 3 0 1 8 0 2 3 1 3 2 1 4 5 2 5 6
输出样例 3 4
#includeiostream
#includecstring
using namespace std;
const int N20010,MN*2;
int h[N],e[M],ne[M],w[M],idx; //头结点、邻接表结点、指针、权、插入的第几个结点。
void add(int a,int b,int c)
{e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx;
}
int dfs(int u,int mid,int fa) //从第u个节点遍历mid为答案fa为父节点
{int res1; //从父节点开始可以遍历到的节点for(int ih[u];~i;ine[i]){int je[i];if(jfa||w[i]mid) continue;//如果次节点边权小于答案说明该节点被删除后无法到达根节点。resdfs(j,mid,u);}return res;
}
int main()
{int T;cinT;while(T--){int n,y;cinny;idx0; //每次输出将邻接表清空memset(h,-1,sizeof(h));for(int i0;in-1;i){int a,b,c;cinabc;add(a,b,c); //树为特殊的无向图add(b,a,c);}int l0,r1e8;while(lr){int mid(lr)/2;if(dfs(0,mid,-1)y) rmid; //当答案小于y时说明答案在y左边rmid;else lmid1;}coutrendl;}return 0;
}
