{"id":370,"date":"2017-02-24T16:02:26","date_gmt":"2017-02-24T08:02:26","guid":{"rendered":"http:\/\/kylelv.com\/?p=370"},"modified":"2017-12-28T14:41:58","modified_gmt":"2017-12-28T06:41:58","slug":"%e6%a8%a1%e6%9d%bf-%e6%a0%91%e9%93%be%e5%89%96%e5%88%86","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=370","title":{"rendered":"\u6a21\u677f  &#8212; \u6811\u94fe\u5256\u5206"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdef6d60430\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fdef6d60430\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86\" title=\"\u6811\u94fe\u5256\u5206\">\u6811\u94fe\u5256\u5206<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0\" title=\"\u9898\u76ee\u63cf\u8ff0\">\u9898\u76ee\u63cf\u8ff0<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E8%BE%93%E5%85%A5\" title=\"\u8f93\u5165\">\u8f93\u5165<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E8%BE%93%E5%87%BA\" title=\"\u8f93\u51fa\">\u8f93\u51fa<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%85%A5\" title=\"\u6837\u4f8b\u8f93\u5165\">\u6837\u4f8b\u8f93\u5165<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%87%BA\" title=\"\u6837\u4f8b\u8f93\u51fa\">\u6837\u4f8b\u8f93\u51fa<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=370\/#%E6%8F%90%E7%A4%BA\" title=\"\u63d0\u793a\">\u63d0\u793a<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h1 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86\"><\/span>\u6811\u94fe\u5256\u5206<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<h2><span class=\"ez-toc-section\" id=\"%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0\"><\/span>\u9898\u76ee\u63cf\u8ff0<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div>\u4e00\u68f5\u6811\u6709<em>n<\/em>\u4e2a\u8282\u70b9\uff0c\u6bcf\u4e2a\u8282\u70b9\u6709\u4e00\u4e2a\u70b9\u6743<em>a<sub>i<\/sub><\/em>\uff0c\u5171\u6709<em>m<\/em>\u4e2a\u64cd\u4f5c\uff1a<\/div>\n<div align=\"center\">\n<table border=\"1\" cellspacing=\"0\" cellpadding=\"0\">\n<tbody>\n<tr>\n<td valign=\"top\" width=\"132\">\n<div>\u64cd\u4f5c\u7f16\u53f7<\/div>\n<\/td>\n<td valign=\"top\" width=\"132\">\n<div>\u64cd\u4f5c\u683c\u5f0f<\/div>\n<\/td>\n<td valign=\"top\" width=\"209\">\n<div>\u8bf4\u660e<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" width=\"132\">\n<div>1.\u66f4\u65b0<\/div>\n<\/td>\n<td valign=\"top\" width=\"132\">\n<div>UPDATE p x<\/div>\n<\/td>\n<td valign=\"top\" width=\"209\">\n<div>\u628a\u70b9<em>p<\/em>\u7684\u6743\u503c\u4fee\u6539\u4e3a<em>x<\/em><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" width=\"132\">\n<div>2.\u67e5\u8be2\u6700\u5927<\/div>\n<\/td>\n<td valign=\"top\" width=\"132\">\n<div>MAX p q<\/div>\n<\/td>\n<td valign=\"top\" width=\"209\">\n<div>\u67e5\u8be2<em>p<\/em>\u5230<em>q<\/em>\u8def\u5f84\u4e2d\u6700\u5927\u70b9\u6743<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" width=\"132\">\n<div>3.\u67e5\u8be2\u548c<\/div>\n<\/td>\n<td valign=\"top\" width=\"132\">\n<div>SUM p q<\/div>\n<\/td>\n<td valign=\"top\" width=\"209\">\n<div>\u67e5\u8be2<em>p<\/em>\u5230<em>q<\/em>\u8def\u5f84\u4e2d\u70b9\u6743\u548c<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"%E8%BE%93%E5%85%A5\"><\/span>\u8f93\u5165<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u7b2c\u4e00\u884c\u4e24\u4e2a\u6574\u6570<em>n<\/em>\u548c<em>m<\/em>\uff1b<\/div>\n<div>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u63a5\u4e0b\u6765\u4e00\u884c\u4e2d<em>n<\/em>\u4e2a\u6574\u6570\u8868\u793a\u521d\u59cb\u70b9\u6743\uff1b<\/div>\n<div>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u63a5\u4e0b\u6765\u884c\u4e2d\u6bcf\u884c\u4e24\u4e2a\u6574\u6570<em>p<\/em>\u548c<em>q<\/em>\uff0c\u8868\u793a<em>p<\/em>\u548c<em>q<\/em>\u4e4b\u95f4\u6709\u4e00\u6761\u8fb9\u76f8\u8fde\uff1b<\/div>\n<div>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u63a5\u4e0b\u6765<em>m<\/em>\u884c\u6bcf\u884c\u4e00\u4e2a\u64cd\u4f5c\u5982\u4e0a\u8868\u6240\u793a\u3002<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"%E8%BE%93%E5%87%BA\"><\/span>\u8f93\u51fa<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div>\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u67e5\u8be2\u64cd\u4f5c\uff0c\u8f93\u51fa\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570\u4e3a\u5bf9\u5e94\u7684\u7b54\u6848\u3002<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%85%A5\"><\/span>\u6837\u4f8b\u8f93\u5165<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<pre class=\"content\"><span class=\"sampledata\">4 3\r\n3 6 8 5\r\n1 2\r\n1 3\r\n2 4\r\nMAX 1 4\r\nUPDATE 1 5\r\nSUM 1 3\r\n<\/span><\/pre>\n<h2><span class=\"ez-toc-section\" id=\"%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%87%BA\"><\/span>\u6837\u4f8b\u8f93\u51fa<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<pre class=\"content\"><span class=\"sampledata\">6\r\n13\r\n<\/span><\/pre>\n<h2><span class=\"ez-toc-section\" id=\"%E6%8F%90%E7%A4%BA\"><\/span>\u63d0\u793a<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/218.62.22.209:8080\/upload\/pimg3687_1.jpg\" alt=\"\" width=\"638\" height=\"80\" \/><\/p>\n<pre class=\"lang:c++ decode:true  \">#include&lt;cstdio&gt;\r\n#include&lt;iostream&gt;\r\nusing namespace std;\r\n#define N 100010\r\ninline int max(int a,int b){return a&gt;b?a:b;}\r\nvoid swap(int &amp;a,int &amp;b){int c=a^b;b=b^c;a=a^c;}\r\ninline int read()\r\n{\r\n    int x=0,f=1;char ch=getchar();\r\n    while(ch&lt;'0'||ch&gt;'9'){if(ch=='-')f=-1;ch=getchar();}\r\n    while(ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-'0';ch=getchar();}\r\n    return x*f;\r\n}\r\nstruct qaz{int fro,to;}e[N&lt;&lt;1];\r\nint tot[N],siz[N],top[N],son[N],dep[N],fa[N],tid[N],tim,rrank[N],lj[N],cnt;\r\nvoid add(int a,int b){e[++cnt].fro=lj[a];e[cnt].to=b;lj[a]=cnt;}\r\nvoid dfs1(int u,int father,int d)\r\n{\r\n    dep[u]=d;\r\n    fa[u]=father;\r\n    siz[u]=1;\r\n    for(int i=lj[u];i;i=e[i].fro)\r\n    {\r\n        int v=e[i].to;\r\n        if(v!=father)\r\n        {\r\n            dfs1(v,u,d+1);  siz[u]+=siz[v];\r\n            if(son[u]==-1||siz[son[u]]&lt;siz[v]) son[u]=v;\r\n        }\r\n    }\r\n}\r\nvoid dfs2(int u,int tp)\r\n{\r\n    top[u]=tp;\r\n    tid[u]=++tim;\r\n    rrank[tim]=u;\r\n    if(son[u]==-1) return;\r\n    dfs2(son[u],tp);\r\n    for(int i=lj[u];i;i=e[i].fro)\r\n    {\r\n        int v=e[i].to;\r\n        if(son[u]!=v&amp;&amp;v!=fa[u]) dfs2(v,v);\r\n    }\r\n}\r\nint n,m,p,q,a[N];\r\nchar ss;\r\nstruct tree{int l,r,maxx,sum;}tr[N&lt;&lt;2];\r\nvoid pu(int x)\r\n{\r\n    tr[x].maxx=max(tr[x&lt;&lt;1].maxx,tr[x&lt;&lt;1|1].maxx);\r\n    tr[x].sum=tr[x&lt;&lt;1].sum+tr[x&lt;&lt;1|1].sum;\r\n}\r\nvoid build(int l,int r,int x)\r\n{\r\n    tr[x].l=l;tr[x].r=r;\r\n    if(l==r)\r\n    {\r\n        tr[x].maxx=a[rrank[l]];\r\n        tr[x].sum=a[rrank[l]];\r\n        return;\r\n    }\r\n    int mid=(l+r)&gt;&gt;1;\r\n    build(l,mid,x&lt;&lt;1);build(mid+1,r,x&lt;&lt;1|1);\r\n    pu(x);\r\n}\r\nvoid xg(int c,int k,int x)\r\n{\r\n    if(tr[x].l==tr[x].r)\r\n    {\r\n        tr[x].sum=tr[x].maxx=k;\r\n        return;\r\n    }\r\n    int mid=(tr[x].l+tr[x].r)&gt;&gt;1;\r\n    if(c&lt;=mid) xg(c,k,x&lt;&lt;1);\r\n    else xg(c,k,x&lt;&lt;1|1);\r\n    pu(x);\r\n}\r\ninline int fdmax(int l,int r,int x)\r\n{\r\n    if(tr[x].l==l&amp;&amp;tr[x].r==r) return tr[x].maxx;\r\n    int mid=(tr[x].l+tr[x].r)&gt;&gt;1;\r\n    if(r&lt;=mid) return fdmax(l,r,x&lt;&lt;1);\r\n    else if(l&gt;mid) return fdmax(l,r,x&lt;&lt;1|1);\r\n    else return max(fdmax(l,mid,x&lt;&lt;1),fdmax(mid+1,r,x&lt;&lt;1|1));\r\n}\r\ninline int fdsum(int l,int r,int x)\r\n{\r\n    if(tr[x].l==l&amp;&amp;tr[x].r==r) return tr[x].sum;\r\n    int mid=(tr[x].l+tr[x].r)&gt;&gt;1;\r\n    if(r&lt;=mid) return fdsum(l,r,x&lt;&lt;1);\r\n    else if(l&gt;mid) return fdsum(l,r,x&lt;&lt;1|1);\r\n    else return fdsum(l,mid,x&lt;&lt;1)+fdsum(mid+1,r,x&lt;&lt;1|1);\r\n}\r\n\r\nint main()\r\n{\r\n    n=read();m=read();\r\n    for(int i=1;i&lt;=n;i++) a[i]=read();\r\n    for(int i=1;i&lt;n;i++)\r\n    {\r\n        p=read();q=read();\r\n        add(p,q);add(q,p);\r\n    }\r\n    for(int i=0;i&lt;=n;i++) son[i]=-1;\r\n    dfs1(1,0,0);\r\n    dfs2(1,1);\r\n    build(1,n,1);\r\n    for(int i=0;i&lt;m;i++)\r\n    {\r\n        ss=' ';\r\n        while(ss&lt;'A'||ss&gt;'Z') ss=getchar();\r\n        p=read();q=read();\r\n        int tmp=0;\r\n        if(ss=='U') xg(tid[p],q,1);\r\n        else if(ss=='M')\r\n        {\r\n            while(top[p]!=top[q])\r\n            {\r\n                if(dep[top[p]]&lt;dep[top[q]]) swap(p,q);\r\n                tmp=max(tmp,fdmax(tid[top[p]],tid[p],1));\r\n                p=fa[top[p]];\r\n            }\r\n            if(dep[p]&gt;dep[q]) swap(p,q);\r\n            tmp=max(tmp,fdmax(tid[p],tid[q],1));\r\n        }\r\n        else if(ss=='S')\r\n        {\r\n            while(top[p]!=top[q])\r\n            {\r\n                if(dep[top[p]]&lt;dep[top[q]]) swap(p,q);\r\n                tmp+=fdsum(tid[top[p]],tid[p],1);\r\n                p=fa[top[p]];\r\n            }\r\n            if(dep[p]&gt;dep[q]) swap(p,q);\r\n            tmp+=fdsum(tid[p],tid[q],1);\r\n        }\r\n        if(ss!='U')printf(\"%d\\n\",tmp);\r\n    }\r\n    return 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u6811\u94fe\u5256\u5206 \u9898\u76ee\u63cf\u8ff0 \u4e00\u68f5\u6811\u6709n\u4e2a\u8282\u70b9\uff0c\u6bcf\u4e2a\u8282\u70b9\u6709\u4e00\u4e2a\u70b9\u6743ai\uff0c\u5171\u6709m\u4e2a\u64cd\u4f5c\uff1a \u64cd\u4f5c\u7f16\u53f7 \u64cd\u4f5c\u683c\u5f0f \u8bf4\u660e 1.\u66f4 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[33,19],"class_list":["post-370","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-33","tag-19"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/370","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=370"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/370\/revisions"}],"predecessor-version":[{"id":371,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/370\/revisions\/371"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=370"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=370"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=370"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}