【日常小测】最大值

Qizy Segment Tree, 数据结构, 解题报告

相关链接

题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/03/5894746723453.png

解题报告

最开始题意看错了，花了一个小时写了一个虚树+主席树，写完之后发现过不了样例 QwQ
正解的话，我们搞一发线段树合就可以了
算是一个比较好玩的线段树合并的模板题吧！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const int M = N * 30;
 
int n,tot,head[N],nxt[N],to[N],cost[N],vout[N];
int fa[N][20],dis[N],dep[N],val[N],HASH[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
class Segment_Tree{
    int root[N],cnt;
    struct Node{int ch[2],lca,sz,id; LL ans,sum;}p[M];
    public:
        inline void insert(int v, int w) {
            insert(root[w], 1, n, v, w);
        }
        inline void Merge(int a, int b) {
            root[a] = merge(root[a], root[b]);
        }
        inline int query(int w) {
            return p[root[w]].id;
        }
        inline Segment_Tree() {
            p[0].ans = -1;
        }
    private:
        void insert(int &w, int l, int r, int pos, int lca) {
            if (w=++cnt, l==r) {
                p[w].lca = lca; p[w].sz = 1; 
            } else {
                int mid = l + r + 1 >> 1;
                if (pos < mid) insert(p[w].ch[0], l, mid-1, pos, lca);
                else insert(p[w].ch[1], mid, r, pos, lca);
            } p[w].id = pos; p[w].ans = 0;
        }
        int merge(int a, int b) {
            if (!a || !b) return a + b;
            if (p[a].ch[0] || p[a].ch[1]) {
                p[a].ch[0] = merge(p[a].ch[0], p[b].ch[0]);
                p[a].ch[1] = merge(p[a].ch[1], p[b].ch[1]);
                int ls = p[a].ch[0], rs = p[a].ch[1]; 
                if (p[ls].ans >= p[rs].ans) p[a].ans = p[ls].ans, p[a].id = p[ls].id;
                else p[a].ans = p[rs].ans, p[a].id = p[rs].id;
            } else {
                int lca = LCA(p[a].lca, p[b].lca);
                LL delta = (dis[p[a].lca] + dis[p[b].lca] - dis[lca] * 2ll) * p[a].sz * p[b].sz;
                delta += p[a].sum * p[b].sz + p[b].sum * p[a].sz;
                p[a].ans = p[a].ans + p[b].ans + delta;
                p[a].sum = p[a].sum + ((LL)dis[p[a].lca] - dis[lca]) * p[a].sz ;
                p[a].sum += p[b].sum + ((LL)dis[p[b].lca] - dis[lca]) * p[b].sz;
                p[a].sz += p[b].sz; p[a].lca = lca;
            } return a;
        }
        inline int LCA(int u, int v) {
            if (dep[u] < dep[v]) swap(u, v);
            for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u=fa[u][i];
            if (u == v) return u;
            for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
            return fa[u][0];
        }
}SGT;
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c;
    to[++E] = v; nxt[E] = head[u]; head[u] = E; 
    to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}
 
void DFS(int w, int f) {
    dep[w] = dep[f] + 1; fa[w][0] = f;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            dis[to[i]] = dis[w] + cost[i];
            DFS(to[i], w);
        }
    } 
}
 
void solve(int w, int f) {
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            solve(to[i], w);
            SGT.Merge(w, to[i]);
        }
    } vout[w] = SGT.query(w);
}
 
int main() {
    n = read();
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        AddEdge(u, v, read());
    }
    for (int i=1;i<=n;i++) HASH[i] = val[i] = read();
    sort(HASH+1, HASH+1+n);
    tot = unique(HASH+1, HASH+1+n) - HASH - 1;
    for (int i=1;i<=n;i++) val[i] = lower_bound(HASH+1, HASH+1+tot, val[i]) - HASH;
    for (int i=1;i<=n;i++) SGT.insert(val[i], i);
    DFS(1, 1);
    for (int j=1;j<=19;j++) for (int i=1;i<=n;i++) 
        fa[i][j] = fa[fa[i][j-1]][j-1];
    solve(1, 1);
    for (int i=1;i<=n;i++) printf("%d\n",HASH[vout[i]]);
    return 0;
}

248 thoughts to “【日常小测】最大值”

  1. Howdy, i read your blog from time to time and i own a similar one and i was just
    curious if you get a lot of spam remarks? If so how do you prevent it, any plugin or anything you can advise?

    I get so much lately it’s driving me insane so any assistance is very much appreciated.

    Reply

  3. Hiya very cool website!! Man .. Beautiful .. Wonderful ..
    I will bookmark your blog and take the feeds also?
    I’m happy to find numerous helpful info here in the submit, we’d like work out more techniques on this regard, thank you for sharing.
    . . . . .

    Reply

  4. I have to thank you for the efforts you have put in penning this website.

    I really hope to see the same high-grade content by you later on as well.
    In truth, your creative writing abilities has motivated me to get my own site now
    😉

    Reply

  5. Hello! I know this is kind of off topic but I was wondering
    which blog platform are you using for this site?
    I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at alternatives for another platform.
    I would be awesome if you could point me in the direction of a good platform.

    Reply

  6. I’ve been exploring for a bit for any high quality articles or blog
    posts on this sort of area . Exploring in Yahoo I at last stumbled upon this web site.
    Reading this info So i am glad to exhibit that I’ve an incredibly good uncanny feeling I came upon exactly what I
    needed. I so much surely will make certain to do not disregard
    this site and provides it a look on a relentless basis.

    Reply

  8. After looking into a number of the articles on your website, I truly appreciate your way of writing a blog.
    I saved as a favorite it to my bookmark site list and will be
    checking back in the near future. Please visit my website as well and tell me what you think.

    Reply

  9. What’s Happening i am new to this, I stumbled upon this I’ve discovered It absolutely helpful and it has helped me out loads.
    I am hoping to contribute & aid other customers like its aided me.
    Great job.

    Reply

  11. I was wondering if you ever considered changing the structure of your site?
    Its very well written; I love what youve got to say. But maybe you could a little more
    in the way of content so people could connect with it
    better. Youve got an awful lot of text for only having 1 or two images.
    Maybe you could space it out better?

    Reply

  14. I was wondering if you ever thought of changing the page layout of
    your blog? Its very well written; I love what youve got
    to say. But maybe you could a little more in the way of content so
    people could connect with it better. Youve got an awful lot of text for only having 1 or
    two pictures. Maybe you could space it out better?

    Reply

  16. I’ve been surfing on-line greater than 3 hours lately, yet I
    by no means found any attention-grabbing article like yours.
    It’s beautiful worth sufficient for me. In my view, if all website owners and
    bloggers made just right content as you did, the net shall be much more
    useful than ever before.

    Reply

  18. Please let me know if you’re looking for a writer for your site.

    You have some really good articles and I believe I would be a good asset.
    If you ever want to take some of the load off, I’d really like to write some material for
    your blog in exchange for a link back to mine.
    Please blast me an e-mail if interested. Many thanks!

    Reply

  20. Link exchange is nothing else except it is only placing the other person’s website
    link on your page at proper place and other person will also do similar in favor of
    you. plenty of fish natalielise

    Reply

  21. My partner and I stumbled over here by a different page and thought I might check things out.

    I like what I see so now i’m following you. Look forward to going over your
    web page again. plenty of fish natalielise

    Reply

  23. Fantastic blog! Do you have any recommendations for aspiring writers?
    I’m hoping to start my own website soon but I’m a little lost on everything.
    Would you propose starting with a free platform like WordPress or go
    for a paid option? There are so many choices out there that I’m totally overwhelmed ..
    Any recommendations? Thank you! natalielise pof

    Reply

  27. It’s perfect time to make some plans for the future and it is time to be
    happy. I’ve read this post and if I could I wish to suggest you
    few interesting things or advice. Perhaps you could write next articles referring to this article.
    I desire to read more things about it!

    Reply

  29. It’s perfect time to make some plans for the future and it’s time to
    be happy. I’ve read this post and if I could I desire to suggest you some interesting
    things or advice. Maybe you could write next articles referring to
    this article. I desire to read more things about it!

    Reply

  31. Good day! This is kind of off topic but I need some advice from an established blog.
    Is it very difficult to set up your own blog?
    I’m not very techincal but I can figure things out pretty quick.

    I’m thinking about creating my own but I’m
    not sure where to begin. Do you have any ideas or suggestions?
    With thanks

    Reply

  33. A motivating discussion is definitely worth comment.
    I do think that you ought to publish more on this subject, it might not
    be a taboo matter but usually people don’t discuss such topics.
    To the next! Kind regards!!

    Reply

  34. We are a bunch of volunteers and opening a new scheme in our community.
    Your web site offered us with useful information to work
    on. You’ve done an impressive task and our entire neighborhood shall be thankful to you.

    Reply

  37. My partner and I stumbled over here coming from a different website and thought I may as well check things out.
    I like what I see so i am just following you. Look forward to
    exploring your web page repeatedly.

    Reply

  39. Hey! I know this is kinda off topic however I’d
    figured I’d ask. Would you be interested in trading links
    or maybe guest writing a blog post or vice-versa? My website covers a lot of the same topics
    as yours and I think we could greatly benefit
    from each other. If you’re interested feel free to shoot me
    an email. I look forward to hearing from you!
    Great blog by the way!

    Reply

  41. Oh my goodness! Amazing article dude! Thanks, However I am experiencing
    problems with your RSS. I don’t know the reason why I cannot
    subscribe to it. Is there anybody getting the same RSS problems?
    Anybody who knows the solution will you kindly respond? Thanks!!

    Reply

  43. With havin so much written content do you ever run into any issues of plagorism or
    copyright infringement? My site has a lot of unique content I’ve either written myself or outsourced but it looks like a lot of it is popping it up all over the web without my permission. Do you know any
    techniques to help reduce content from being stolen? I’d
    genuinely appreciate it.

    Reply

  47. Pretty portion of content. I simply stumbled upon your blog and in accession capital to say that I
    acquire actually loved account your blog posts.
    Any way I will be subscribing to your augment or even I success you access consistently quickly.

    Reply

  50. I’ve been surfing online more than 3 hours today, yet I never
    found any interesting article like yours. It is pretty worth enough for me.

    In my view, if all web owners and bloggers made good content as you did, the web will be
    a lot more useful than ever before.

    Reply

  65. Hello, I do think your web site could be having internet browser
    compatibility problems. When I take a look at your blog
    in Safari, it looks fine but when opening in Internet Explorer, it’s got
    some overlapping issues. I just wanted to give you a quick
    heads up! Apart from that, great site!

    Reply

  67. I simply couldn’t depart your web site prior to suggesting that I extremely enjoyed the usual information a person supply in your visitors?
    Is going to be back regularly in order to check up on new posts

    Reply

  72. Hey There. I found your blog using msn. This is an extremely
    well written article. I’ll be sure to bookmark it and
    come back to read more of your useful information. Thanks for the post.
    I will definitely comeback.

    Reply

  74. Hi there, i read your blog from time to time and
    i own a similar one and i was just wondering if you get a lot of spam
    comments? If so how do you prevent it, any plugin or anything
    you can recommend? I get so much lately it’s driving me insane so any help is very
    much appreciated.

    Reply

  77. Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your website?
    My website is in the very same area of interest as yours and my visitors would definitely benefit from some of
    the information you provide here. Please let me know if
    this okay with you. Many thanks!

    Reply

  87. After looking into a few of the blog posts on your web site, I honestly appreciate your technique of blogging.

    I bookmarked it to my bookmark webpage list and will
    be checking back in the near future. Please check out my
    web site too and tell me how you feel.

    Reply

  99. Write more, thats all I have to say. Literally,
    it seems as though you relied on the video to make your point.
    You obviously know what youre talking about, why throw away your intelligence on just posting videos to your
    weblog when you could be giving us something informative to read?

    Reply

  115. It is the best time to make a few plans for the
    long run and it is time to be happy. I’ve read this publish and
    if I may I wish to suggest you few fascinating things or tips.
    Perhaps you could write next articles relating to this article.

    I desire to learn more issues about it!

    Reply

  116. Thanks for sharing superb informations. Your website is so cool. I am impressed by the details that you¦ve on this site. It reveals how nicely you understand this subject. Bookmarked this website page, will come back for more articles. You, my friend, ROCK! I found just the information I already searched all over the place and simply could not come across. What an ideal site.

    Reply

  134. “4 Songs for the Club” Is a 4 song CD-EP from B-Rock, For Dj’s and Bars and Dance clubs ..”Dance”Features Rockman doing the electronic Vocals on the Chorus. A hand clapping song to get people on tha dance floor ….”Mix It With Tha Water”. Features B-Rocks Team member Pif .. Tha song is an urban street tale with a great Trap Beat….”I Like It Straight” is Bound to be a New Club/ Bar Anthem for the DJ’s to get the crowds up on their feet and to get another drink..LOL…and “Crack Them bottle (Get Fucked Up)” well that’s a story that all party goers live on the weekend! … 4 Dance Hits 4 tha Club.. a great EP for any DJ to have

    Reply

  162. Hey! Someone in my Facebook group shared this website
    with us so I came to look it over. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
    Exceptional blog and fantastic design and style.

    Reply

  180. We stumbled over here from a different web address and thought I should check things out.
    I like what I see so now i am following you.
    Look forward to looking at your web page yet again.

    Reply

  199. Great items from you, man. I’ve have in mind your stuff previous
    to and you’re simply too magnificent. I actually like what you’ve got right here, really like
    what you are saying and the way during which you
    assert it. You’re making it enjoyable and you continue to care for to keep it wise.
    I can’t wait to learn far more from you. This is really a wonderful website.

    Reply

  207. Thanks for another informative blog. Where else may just I get that kind of information written in such a perfect means? I’ve a challenge that I am just now running on, and I have been at the look out for such info.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *