【CodeChef TREEP】Period on tree

Qizy Fenwick Tree, Hash, 字符串, 数据结构, 解题报告

相关链接

题目传送门：https://www.codechef.com/NOV15/problems/TREEP
中文题面：http://www.codechef.com/download/translated/NOV15/mandarin/TREEP.pdf
官方题解：https://discuss.codechef.com/questions/76897/treep-editorial

题目大意

给定一个$n(n \le 200000)$个结点的树，每条边上有一个小写字母
定义$Str_{u,v}$为从$u$走到$v$将路径上的小写字母按顺序拼起来组成的字符串
给定$m(m \le 200000)$个操作，操作分两类：

  1. 输入$u,v$，询问$Str_{u,v}$的循环节最短为多长
  2. 输入$u,v,c$，表示将$u \to v$这条边上的字符改成$c$

解题报告

这么奇怪的题目，一看就只能是$Hash$来做
我们不难发现，若循环节为$l$,串长$len$，那么$\forall x \in (l,len]$若$x \equiv 0(\bmod l)$则$x$也是循环节
于是如果我们可以$O(\log n)$判定$l$是不是原串的循环节，我们就可以在$O(n \log^2 n)$的时间复杂度内解决这个问题了

我们发现，若是循环节，那么开头那一段的$Hash$值不仅可以整除整个串的$Hash$值，而且等于一个等比数列
于是我们就可以用BIT维护一个到根的前缀和，然后将判定优化到$O(\log n)$

Code

这是考试的代码，似乎没写多组数据，CC上交不了QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
const int SED = 37;
const int MOD = 1000000009;
 
int n,m,head[N],to[M],nxt[M],cost[M],dep[N],beg[N],END[N]; 
int POW[M],tot,pri[N],vis[N],sur[N],fa[N][20],val[N];
char pat[5];
 
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;
}
 
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;
}
 
class FenwickTree{
    #define lowbit(x) ((x)&(-(x)))
    int sum[N];
    public:
        inline void modify(int l, int r, int v) {
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
        }   
        inline int query(int p) {
            int ret = 0; p = beg[p];
            for (int i=p;i<=n;i+=lowbit(i)) 
                ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}up,dw;
 
inline void prework() {
    POW[0] = sur[1] = 1; 
    for (int i=1;i<M;i++) POW[i] = (LL)POW[i-1] * SED % MOD;
    for (int i=2;i<N;i++) {
        if (!vis[i]) pri[++tot] = i, sur[i] = i;
        for (int j=1;j<=tot&&i*pri[j]<N;j++) {
            vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u=fa[u][j];
    if (u == v) return u;
    for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
    return fa[u][0];
}
 
void DFS(int w, int f) {
    static int dfs_cnt = 0; 
    beg[w] = ++dfs_cnt;
    fa[w][0] = f; dep[w] = dep[f] + 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            val[to[i]] = cost[i];
            DFS(to[i], w);
        }
    }
    END[w] = dfs_cnt;
    up.modify(beg[w], END[w], (LL)val[w] * POW[n-dep[w]+1] % MOD);
    dw.modify(beg[w], END[w], (LL)val[w] * POW[dep[w]] % MOD); 
}
 
inline int FA(int u, int k) {
    for (int t=0;k;k>>=1,t++) 
        if (k&1) u = fa[u][t];
    return u;
}
 
inline int query(int u, int v, int lca, int k) {
    if (dep[u] - dep[lca] >= k) {
        int ret = (up.query(u) - up.query(FA(u, k))) % MOD;
        return (((LL)ret * POW[dep[u]-1] % MOD) + MOD) % MOD;
    } else {
        int ret = (up.query(u) - up.query(lca)) % MOD;
        ret = (LL)ret * POW[dep[u] - 1] % MOD;
        int res = dep[u] + dep[v] - (dep[lca] << 1) - k;
        res = (dw.query(FA(v, res)) - dw.query(lca)) % MOD;
        res = (LL)res * POW[n + dep[u] - (dep[lca] << 1) - 1] % MOD;
        return ((res + ret) % MOD + MOD) % MOD;
    }
}
 
inline int Pow(int w, int t) {
    int ret = 1;
    for (;t;t>>=1,w=(LL)w*w%MOD)
        if (t&1) ret=(LL)ret*w%MOD;
    return ret;
}   
 
inline int query(int u, int v) {
    int lca = LCA(u, v); tot = 0;
    int len = dep[u] + dep[v] - (dep[lca] << 1);
    int STA = query(u, v, lca, len), ori = len;
    for (int c,w=len;c=sur[w],w>1;) {
        pri[++tot] = c; vis[tot] = 0;
        for (;w%c==0;w/=c) vis[tot]++; 
    }
    for (int i=1,sta,cur,PRI;i<=tot;i++) {
        PRI = pri[i];
        for (int j=1;j<=vis[i];j++) {
            sta = (LL)(Pow(POW[len/PRI], ori/len*PRI) - 1) * Pow(POW[len/PRI]-1, MOD-2) % MOD;
            cur = (LL)STA * Pow(query(u, v, lca, len / PRI), MOD-2) % MOD;
            if (sta==cur) len /= PRI;
            else break;
        }
    }
    return len;
}
 
int main() {
    prework();
    n = read(); 
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        AddEdge(u, v, pat[1]-'a'+1);
    }
    DFS(1, 1);
    for (int j=1;j<20;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    } 
    m = read(); 
    for (int i=1,u,v,c;i<=m;i++) {
        if (read() == 1) {
            u = read(); v = read();
            printf("%d\n",query(u, v));
        } else {
            u = read(); v = read();
            if (dep[u] > dep[v]) swap(u, v);
            scanf("%s",pat+1); c = pat[1]-'a'+1;
            if (c == val[v]) continue;
            up.modify(beg[v], END[v], (LL)(c - val[v]) * POW[n-dep[v]+1] % MOD);
            dw.modify(beg[v], END[v], (LL)(c - val[v]) * POW[dep[v]] % MOD);
            val[v] = c;
        }
    } 
    return 0;
}

338 thoughts to “【CodeChef TREEP】Period on tree”

  3. My brother recommended I may like this web site.
    He was once totally right. This put up actually
    made my day. You cann’t consider simply how much time I had spent for this info!
    Thank you!

    Reply

  5. Appreciating the time and effort you put into your blog and in depth information you present.

    It’s great to come across a blog every once in a while that isn’t
    the same outdated rehashed information. Excellent read!
    I’ve saved your site and I’m adding your RSS feeds to my Google account.

    Reply

  6. Hello there! 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 issues with
    hackers and I’m looking at options for another platform.
    I would be great if you could point me in the direction of a good
    platform.

    Reply

  8. I really like your blog.. very nice colors & theme. Did you design this website yourself or did you hire someone to do it for you?
    Plz reply as I’m looking to design my own blog and would like
    to know where u got this from. many thanks

    Reply

  9. Howdy! Quick question that’s completely off topic. Do you know how to make
    your site mobile friendly? My blog looks weird when browsing from my apple iphone.
    I’m trying to find a template or plugin that might be able to resolve this issue.
    If you have any suggestions, please share. Appreciate it!

    Reply

  11. I truly love your blog.. Great colors & theme. Did you create this
    web site yourself? Please reply back as I’m planning to create my own personal site and want to
    find out where you got this from or exactly what
    the theme is named. Thank you!

    Reply

  12. Having read this I believed it was very informative. I appreciate
    you finding the time and effort to put this article together.
    I once again find myself personally spending a lot of time both reading and commenting.
    But so what, it was still worth it!

    Reply

  13. An impressive share! I’ve just forwarded this onto a friend
    who was conducting a little homework on this. And he actually ordered me lunch due to the fact that I discovered
    it for him… lol. So allow me to reword this….
    Thank YOU for the meal!! But yeah, thanx for spending time to discuss
    this issue here on your blog.

    Reply

  15. Aw, this was an extremely good post. Taking a few minutes
    and actual effort to produce a superb article… but what can I say… I procrastinate a lot and don’t seem
    to get anything done.

    Reply

  18. Howdy! I know this is somewhat off topic but I was wondering
    if you knew where I could locate a captcha plugin for my comment form?
    I’m using the same blog platform as yours and I’m having problems finding one?
    Thanks a lot!

    Reply

  22. Neat blog! Is your theme custom made or did you download it from somewhere?

    A theme like yours with a few simple tweeks would really make my blog shine.

    Please let me know where you got your design. With thanks natalielise pof

    Reply

  25. I am really enjoying the theme/design of your site.
    Do you ever run into any browser compatibility issues? A couple of my blog audience have complained about my blog not working correctly in Explorer but looks great in Safari.
    Do you have any recommendations to help fix this problem?

    Reply

  32. I blog often and I really appreciate your information. Your article has really
    peaked my interest. I’m going to bookmark your
    website and keep checking for new details about
    once per week. I opted in for your Feed too.

    Reply

  33. Terrific work! That is the kind of info that are
    meant to be shared around the net. Shame on Google for not positioning
    this put up higher! Come on over and visit my website .

    Thank you =)

    Reply

  35. Admiring the dedication you put into your blog and in depth information you provide.
    It’s awesome to come across a blog every once in a
    while that isn’t the same unwanted rehashed material.
    Wonderful read! I’ve bookmarked your site and I’m including your RSS feeds to my Google
    account.

    Reply

  36. Cool blog! Is your theme custom made or did you download it from
    somewhere? A design like yours with a few simple
    tweeks would really make my blog stand out. Please
    let me know where you got your theme. Thanks a lot

    Reply

  37. Nice blog here! Also your website loads up very fast!
    What web host are you using? Can I get your affiliate
    link to your host? I wish my web site loaded up as fast as
    yours lol

    Reply

  39. Thanks for your personal marvelous posting! I truly
    enjoyed reading it, you might be a great author.I will
    be sure to bookmark your blog and will often come back from now on. I
    want to encourage yourself to continue your great posts, have a nice morning!

    Reply

  40. I do not even know how I ended up here, but I thought this
    post was good. I do not know who you are but certainly you’re going to a famous
    blogger if you aren’t already 😉 Cheers!

    Reply

  41. Excellent post. I was checking continuously this blog and I’m impressed!

    Extremely helpful info specially the last part 🙂 I
    care for such info much. I was seeking this particular info for a
    very long time. Thank you and good luck.

    Reply

  43. Its like you read my mind! You appear to know so much about this, like
    you wrote the book in it or something. I think that you could
    do with a few pics to drive the message home
    a little bit, but instead of that, this is excellent blog.
    A fantastic read. I will certainly be back.

    Reply

  44. Thanks for some other informative website.
    Where else may just I get that kind of info written in such an ideal manner?
    I have a undertaking that I’m simply now working on, and I have been on the look out for such information.

    Reply

  46. I am now not certain the place you’re getting your info, but great topic.

    I needs to spend some time learning much more or figuring out more.
    Thanks for magnificent info I was searching for this info
    for my mission.

    Reply

  48. I got this web site from my pal who shared with me on the topic of this site and at the moment
    this time I am browsing this web page and reading very informative articles or reviews at this time.

    Reply

  50. Good post. I learn something totally new and challenging on blogs I stumbleupon every
    day. It’s always interesting to read through content from other writers and use something from
    their sites.

    Reply

  51. Can I simply just say what a comfort to find a person that actually knows what they’re discussing online.
    You actually understand how to bring a problem to light and make it important.
    More and more people ought to look at this
    and understand this side of your story. I was surprised you are not more
    popular since you certainly have the gift.

    Reply

  55. Hi, I do believe this is an excellent website. I stumbledupon it 😉 I may revisit once again since i have bookmarked it.

    Money and freedom is the greatest way to change, may you be rich and continue to guide other people.

    Reply

  56. Pretty section of content. I just stumbled upon your website and in accession capital to say that
    I acquire in fact enjoyed account your weblog posts.

    Anyway I will be subscribing in your feeds or even I fulfillment you get admission to persistently fast.

    Reply

  59. I am curious to find out what blog system you have been working with?
    I’m having some small security problems with my latest site and I’d like to find something more safe.
    Do you have any recommendations?

    Reply

  85. Hello, I think your site might be having browser compatibility issues.
    When I look at your blog in Opera, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that, excellent blog!

    Reply

  89. Just want to say your article is as surprising. The clearness for your publish is simply spectacular and i can suppose you’re an expert in this subject.

    Well with your permission let me to grasp your feed to stay
    updated with forthcoming post. Thank you one million and please keep
    up the rewarding work.

    Reply

  101. You are so cool! I don’t believe I’ve read through a single thing like this before.
    So wonderful to discover another person with unique thoughts on this issue.
    Really.. many thanks for starting this up. This web site is something that’s needed
    on the web, someone with a little originality!

    Reply

  106. Whoa! This blog looks just like my old one! It’s
    on a entirely different topic but it has pretty much the same layout and
    design. Excellent choice of colors!

    Reply

  122. Excellent blog here! Also your web site loads up fast! What web host are you using?

    Can I get your affiliate link to your host? I wish my website loaded up as quickly as yours lol

    Reply

  128. Hello! This is my first comment here so I just wanted to give a quick shout out and
    tell you I genuinely enjoy reading through your blog posts.
    Can you recommend any other blogs/websites/forums that go over the same topics?
    Thanks a lot!

    Reply

  132. I’ve been browsing online greater than three hours as of
    late, yet I never discovered any attention-grabbing article like
    yours. It’s pretty worth sufficient for me.
    In my opinion, if all site owners and bloggers made good content material as you probably did,
    the web might be a lot more useful than ever before.

    Reply

  147. I think this is among the most significant info for me. And i
    am glad reading your article. But want to remark on few
    general things, The website style is wonderful, the articles is really excellent : D.
    Good job, cheers

    Reply

  150. I am extremely impressed with your writing skills and also with the layout on your blog.
    Is this a paid theme or did you modify it yourself? Either way keep
    up the excellent quality writing, it’s rare to see
    a nice blog like this one these days.

    Reply

  152. Hi! I could have sworn I’ve visited this site before but after
    looking at many of the articles I realized it’s new to me.
    Anyways, I’m definitely delighted I stumbled upon it and I’ll be bookmarking it and checking back
    often!

    Reply

  156. Hmm is anyone else experiencing problems with the
    images on this blog loading? I’m trying to find out if its a problem on my end or if it’s the blog.
    Any feedback would be greatly appreciated.

    Reply

  169. It’s actually a cool and useful piece of information.
    I’m happy that you shared this useful info with us. Please stay us informed like
    this. Thank you for sharing.

    Reply

  188. I like the helpful information you provide in your articles.
    I will bookmark your weblog and check again here
    regularly. I’m quite sure I will learn many new stuff
    right here! Best of luck for the next!

    Reply

  194. Hi there, I found your web site by the use of Google at the same time as searching for a related subject,
    your site came up, it appears to be like great. I’ve bookmarked it in my google bookmarks.

    Hello there, just became alert to your blog through Google,
    and found that it’s really informative. I’m going to be careful for brussels.
    I will be grateful if you happen to proceed this in future.
    Numerous other folks might be benefited
    from your writing. Cheers!

    Reply

  229. Aw, this was a very nice post. Finding the time and actual effort to produce
    a really good article… but what can I say… I procrastinate
    a whole lot and never manage to get anything done.

    Reply

  233. Heya i am for the first time here. I came across this board and I find It really useful & it helped me out a lot.

    I hope to give something back and aid others like you
    aided me.

    Reply

  248. i enjoy to read all comments here! i really like the wesite you share on us .I appreciate the effort you made.Very informative idea.i want to invite you to visit my site please try it.thank you so much

    Reply

  276. Nice blog here! Also your site loads up very fast!
    What host are you using? Can I get your affiliate
    link to your host? I wish my website loaded up as quickly as yours lol

    Reply

  298. Have you ever thought about adding a little bit more than just your articles? I mean, what you say is important and all. However think about if you added some great photos or videos to give your posts more, “pop”! Your content is excellent but with images and clips, this site could undeniably be one of the greatest in its field. Terrific blog!|

    Reply

  320. Hello there, simply changed into alert to your blog through Google, and located that it is really informative. I’m going to watch out for brussels. I will appreciate if you happen to continue this in future. Lots of people might be benefited from your writing. Cheers!|

    Reply

  337. Hi, Neat post. There is an issue together with your website in internet explorer, may check this? IE nonetheless is the market chief and a big section of folks will leave out your wonderful writing due to this problem.|

    Reply

Leave a Reply

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