页面精美的网站,公司logo素材,网站建设做一个要多久,百度收录最快的网站正题 题目大意
有一颗树#xff0c;求一条路径长度k#xff0c;要求S≤k≤ES\leq k\leq ES≤k≤E#xff0c;求最小的k。 解题思路
其实对于每个点进行点分治#xff0c;每次将整棵子树的路径加入平衡树#xff0c;然后在统计一次答案。时间复杂度O(n2)O(n^2)O(n2)。 之…正题 题目大意
有一颗树求一条路径长度k要求S≤k≤ES\leq k\leq ES≤k≤E求最小的k。 解题思路
其实对于每个点进行点分治每次将整棵子树的路径加入平衡树然后在统计一次答案。时间复杂度O(n2)O(n^2)O(n2)。 之后我们发现其实每次就找该子树的重心继续不用遍历整棵子树。时间复杂度O(能过)O(能过)O(能过) code
#includecstdio
#includeset
#includealgorithm
using namespace std;
const int N100100;
struct node{int to,w,next;
}a[N*3];
setint ga;
int siz[N],ls[N],v[N],root,S,E,n,f[N],ans,tot,x,y,w;
void addl(int x,int y,int w)
{a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
void groot(int x,int fa)//寻找重心
{siz[x]1;f[x]0;for(int ils[x];i;ia[i].next)if(a[i].to!fa!v[a[i].to]){groot(a[i].to,x);siz[x]siz[a[i].to];f[x]max(f[x],siz[a[i].to]);}f[x]max(f[x],n-siz[x]);if (f[x]f[root]) rootx;
}
void dfs(int x,int fa,int w,int flag)//点分治
{if(flag) ga.insert(w);else{if(SwwE) ansmin(ans,E);int maxs*--ga.end();if (wmaxsS){int fndw*ga.lower_bound(S-w);if (SfndfndE) ansmin(ans,fnd);}}for(int ils[x];i;ia[i].next)if (!v[a[i].to]a[i].to!fa)dfs(a[i].to,x,wa[i].w,flag);
}
void dp(int x)
{v[x]1;ga.clear();ga.insert(0);for(int ils[x];i;ia[i].next)if(!v[a[i].to]){dfs(a[i].to,x,a[i].w,0);//根到他的路径加入平衡树dfs(a[i].to,x,a[i].w,1);//统计答案}for(int ils[x];i;ia[i].next)if(!v[a[i].to]){nsiz[a[i].to];root0;groot(a[i].to,0);//寻找重心dp(root);//从重心继续分治}
}
int main()
{scanf(%d%d%d,n,S,E);for(int i1;in;i){scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}ansf[0]2147483647;groot(1,0);dp(root);if(ansE) ans-1;printf(%d,ans);
}
