【学习笔记】CF1783G Weighed Tree Radius

这篇具有很好参考价值的文章主要介绍了【学习笔记】CF1783G Weighed Tree Radius。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

如果 w v ( u ) w_v(u) wv(u)指代的就是直径,或者说我们再添一项 a v a_v av,那么我们几乎就做完了。

于是自然而然想到换一个定义: d ( u , v ) = dist ( u , v ) + a u + a v d(u,v)=\text{dist}(u,v)+a_u+a_v d(u,v)=dist(u,v)+au+av

发现这样转化过后,设直径的两个端点为 u , v u,v u,v,那么 e ( x ) + w x = max ⁡ ( d ( u , x ) , d ( v , x ) ) e(x)+w_x=\max(d(u,x),d(v,x)) e(x)+wx=max(d(u,x),d(v,x))。最后要求 min ⁡ ( e x ) \min(e_x) min(ex),感觉又不行了!

还可以继续转化!考虑此时第 i i i个点对应的树上的节点一定是叶子,那么设这个叶子的父亲为 y y y e ( x ) e(x) e(x)实际上就等于 max ⁡ ( d ( u , y ) , d ( v , y ) ) \max(d(u,y),d(v,y)) max(d(u,y),d(v,y))。又因为求的是 min ⁡ ( e x ) \min(e_x) min(ex),所以答案其实就是整棵树中偏心距的最小值!

那么直接用线段树维护直径的两个端点,然后在直径上二分就做完了!

复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)

remark \text{remark} remark 感觉最近的题目需要转化的地方越来越多了!文章来源地址https://www.toymoban.com/news/detail-599224.html

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db double
#define inf 0x3f3f3f3f
using namespace std;
const int N=4e5+5;
int n,Q,a[N];
vector<int>G[N];
int b[N],cnt,ps[N],dep[N];
int fa[N][20];
void dfs(int u,int topf){
    dep[u]=dep[topf]+1;
    fa[u][0]=topf;for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    b[++cnt]=u,ps[u]=cnt;
    for(auto v:G[u]){
        if(v!=topf)dfs(v,u),b[++cnt]=u;
    }
}
int f[N][20],Log[N];
int Max(int x,int y){
    return dep[x]<dep[y]?x:y;
}
int Lca(int x,int y){
    x=ps[x],y=ps[y];
    if(x>y)swap(x,y);
    int k=Log[y-x+1];
    return Max(f[x][k],f[y-(1<<k)+1][k]);
}
int dist(pair<int,int>x){
    if(x.fi==x.se)return 0;
    return dep[x.fi]+dep[x.se]-2*dep[Lca(x.fi,x.se)]+a[x.fi]+a[x.se];
}
int dist2(pair<int,int>x){
    return dep[x.fi]+dep[x.se]-2*dep[Lca(x.fi,x.se)]+a[x.fi];
}
pair<int,int>Max(pair<int,int>x,pair<int,int>y){
    if(x==make_pair(0,0)||y==make_pair(0,0))return make_pair(x.fi+y.fi,x.se+y.se);
    return dist(x)>dist(y)?x:y;
}
pair<int,int>t[N<<2];
pair<int,int>merge(pair<int,int>x,pair<int,int>y){
    int a[4]={x.fi,x.se,y.fi,y.se};
    pair<int,int>tmp;
    for(int i=0;i<4;i++){
        for(int j=i+1;j<4;j++){
            tmp=Max(tmp,make_pair(a[i],a[j]));
        }
    }
    return tmp;
}
void pushup(int p){
    t[p]=merge(t[p<<1],t[p<<1|1]);
}
void build(int p,int l,int r){
    if(l==r){
        t[p]=make_pair(l,l);
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int x){
    if(l==r)return;
    int mid=l+r>>1;
    x<=mid?modify(p<<1,l,mid,x):modify(p<<1|1,mid+1,r,x);
    pushup(p);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        G[x].pb(y),G[y].pb(x);
    }
    dfs(1,0);for(int i=2;i<=cnt;i++)Log[i]=Log[i/2]+1;
    for(int i=1;i<=cnt;i++)f[i][0]=b[i];
    for(int j=1;j<20;j++){
        for(int i=1;i<=cnt-(1<<j)+1;i++){
            f[i][j]=Max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
    build(1,1,n);
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int x,v;cin>>x>>v;
        a[x]=v,modify(1,1,n,x);
        int U=t[1].fi,V=t[1].se,diam=dist(make_pair(U,V));
        int lca=Lca(U,V),res=inf;
        if(dist2(make_pair(U,lca))<=diam/2){
            x=V;
            for(int j=19;j>=0;j--){
                if(dep[fa[x][j]]>=dep[lca]&&dist2(make_pair(V,fa[x][j]))<=diam/2){
                    x=fa[x][j];
                }
            }
        }
        else{
            x=U;
            for(int j=19;j>=0;j--){
                if(dep[fa[x][j]]>=dep[lca]&&dist2(make_pair(U,fa[x][j]))<=diam/2){
                    x=fa[x][j];
                }
            }
        }
        res=min(res,max(dist2({U,x}),dist2({V,x})));
        if(dep[fa[x][0]]>=dep[lca])res=min(res,max(dist2({U,fa[x][0]}),dist2({V,fa[x][0]})));
        cout<<res<<"\n";
    }
}

到了这里,关于【学习笔记】CF1783G Weighed Tree Radius的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • CF1120 D. Power Tree 巧妙的图论转化

    传送门 [前题提要]:无 题目描述: 考虑对一个点的子树的所有 叶子节点 进行增减任意值.不难联想到对一个点的子树的 所有节点 增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改. 考虑记录一个点的所有叶子节点,并且按照 d f s dfs df s 序将其

    2024年02月10日
    浏览(36)
  • 【学习笔记】CF573E Bear and Bowling

    感觉贪心的做法比较自然🤔,推荐 这篇博客 非常经典 牛逼 的贪心思路: 考虑每次加入一个数,位置 i i i 的贡献为 V i = k i × a i + b i V_i=k_itimes a_i+b_i V i ​ = k i ​ × a i ​ + b i ​ ,其中 k i k_i k i ​ 表示 i i i 以前被选的位置的个数, b i b_i b i ​ 表示 i i i 以后被选的数的

    2024年02月07日
    浏览(31)
  • 【学习笔记】CF1835D Doctor‘s Brown Hypothesis

    有点难😅 发现 x , y x,y x , y 在一个强连通块内,这样一定有环🤔 发现可以找到强连通块内所有环长度的 gcd ⁡ gcd g cd ,这样从 x x x 到 y y y 的所有路径的长度都模这个数同余,又因为 K K K 非常大,所以我们总可以遍历整个强连通块并走若干个环,因此只需要从 x x x 到 y y

    2024年02月09日
    浏览(28)
  • 【学习笔记】CF576D Flights for Regular Customers

    不同于传统的最短路,当我们走到一个节点的时候,还要记录此时经过的边数才能完成转移。但是第二维太大了,太抽象了! 看到 m m m 这么小,很难不想到离散化。那么设 f i , j f_{i,j} f i , j ​ 表示当第 i i i 条边出现时,在节点 j j j 是否可行,注意这是 01 01 01 状态。转移非

    2024年02月12日
    浏览(29)
  • 【学习笔记】CF582D Number of Binominal Coefficients

    注意 P P P 事实上不会影响复杂度,因为关于组合数,我们有一个非常经典的结论: ( n + m m ) binom{n+m}{m} ( m n + m ​ ) 包含的 P P P 的幂的次数等于 n n n 和 m m m 在 P P P 进制下做加法的进位次数。这样,我们只需要关心进位的次数,而不必知道每一位具体是多少。 这个结论的证

    2024年02月12日
    浏览(28)
  • 【学习笔记】CODE FESTIVAL 2017 Final G. Tree MST

    感觉是一道典中典题目! 首先发现一个性质,假设 ( x , y ) (x,y) ( x , y ) 在最终的答案当中,那么对于 x → y xto y x → y 这条链上的任意节点 z z z ,应该满足 w z ≥ min ⁡ ( w x , w y ) w_zge min(w_x,w_y) w z ​ ≥ min ( w x ​ , w y ​ ) 。 这样我们每次把权值最小的点取出来作为根,然

    2024年02月15日
    浏览(40)
  • 机器学习 | 决策树 Decision Tree

    —— 分而治之,逐个击破                 把特征空间划分区域                 每个区域拟合简单模型                 分级分类决策 举例: 特征选择、节点分类、阈值确定                 熵本身代表不确定性,是不确定性的一种度量。     

    2024年02月03日
    浏览(44)
  • 【机器学习基础】决策树(Decision Tree)

    🚀 个人主页 :为梦而生~ 关注我一起学习吧! 💡 专栏 :机器学习 欢迎订阅!后面的内容会越来越有意思~ ⭐ 特别提醒 :针对机器学习,特别开始专栏:机器学习python实战 欢迎订阅!本专栏针对机器学习基础专栏的理论知识,利用python代码进行实际展示,真正做到从基础

    2024年02月20日
    浏览(39)
  • 机器学习算法之决策树(decision tree)

    决策树(Decision Tree,又称为判定树)算法是机器学习中常见的一类算法,是一种以树结构形式表达的预测分析模型。决策树属于监督学习(Supervised learning),根据处理数据类型的不同,决策树又为分类决策树与回归决策树。最早的的决策树算法是由Hunt等人于1966年提出,Hunt算法

    2024年02月13日
    浏览(48)
  • 关于credal set和credal decision tree的一点思考(其实就是论文笔记)

    阅读Abellán老师的Credal-C4.5时,发现好难。。。然后又额外补充了一些论文,终于稍微懂一点点了,所以记录如下。 credal set在DS theory的定义如下 [1]: 这句话的意思是(证据理论中的)credal set是一个概率的凸集,这里面的概率p(x)受到上界pl函数和下界bel函数的控制(约束),

    2024年02月12日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包