{"id":25,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-20\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-20","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-20\/","title":{"rendered":"2020-08-20"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2550&pid=5<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n

L\u56fd\u4e00\u5171\u6709N\u5ea7\u57ce\u9547\uff0c\u5f00\u59cb\u65f6\u5b83\u4eec\u4e24\u4e24\u4e0d\u8fde\u901a\u3002L\u56fd\u8ba1\u5212\u4f9d\u6b21\u5efa\u9020N-1\u6761\u9053\u8def\uff0c\u628a\u6240\u6709\u57ce\u9547\u8fde\u901a\u8d77\u6765\u3002\u6bcf\u5efa\u5b8c\u4e00\u6761\u9053\u8def\uff0c\u4f60\u9700\u8981\u56de\u7b54\u8fd9\u6761\u9053\u8def\u6240\u5728\u8fde\u901a\u5757\u5185\u8ddd\u79bb\u6700\u8fdc\u7684\u4e24\u5ea7\u57ce\u9547\u4e4b\u95f4\u7684\u8ddd\u79bb\u3002\u4e24\u5ea7\u57ce\u9547\u4e4b\u95f4\u7684\u8ddd\u79bb\u5b9a\u4e49\u4e3a\u4ece\u4e00\u5ea7\u8d70\u5230\u53e6\u4e00\u5ea7\u6240\u9700\u8981\u7ecf\u8fc7\u7684\u6700\u5c11\u9053\u8def\u6570\u3002<\/p>\n

<\/a>\u8f93\u5165<\/h6>\n

\u7b2c\u4e00\u884c\u4e00\u4e2a\u6574\u6570N\uff0c\u8868\u793a\u57ce\u9547\u7684\u6570\u91cf\u3002
\u63a5\u4e0b\u6765N-1\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u6574\u6570ai,bi\u8868\u793a\u63a5\u4e0b\u6765\u5efa\u7684\u9053\u8def\u8fde\u901a\u7684\u4e24\u5ea7\u57ce\u9547\u3002
\u4fdd\u8bc1N-1\u6761\u9053\u8def\u80fd\u591f\u4f7f\u6240\u6709\u57ce\u9547\u8fde\u901a\u3002<\/p>\n

<\/a>\u8f93\u51fa<\/h6>\n

\u8f93\u51faN-1\u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u6574\u6570\u8868\u793a\u5efa\u5b8c\u7b2ci\u6761\u9053\u8def\u540e\u7684\u7b54\u6848\u3002<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n
5\n3 5\n3 4\n1 2\n1 3\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n
1\n2\n1\n3\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h6>\n
\u5bf9\u4e8e20%\u7684\u6570\u636e\uff0cn\u2264300;
 \u5bf9\u4e8e50%\u7684\u6570\u636e\uff0cn\u22642000;
 \u5bf9\u4e8e\u53e6\u591620%\u7684\u6570\u636e\uff0c\u4fdd\u8bc1bi=i+1,ai<=i;
 \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0cn\u2264300000\u3002<\/p>\n
<\/a>\u89e3\u6790<\/h6>\n
\u53c2\u8003\u4e8e\uff1ahttps:\/\/blog.csdn.net\/qq_43857314\/article\/details\/108108130<\/a>
 lca+st\u7b97\u6cd5\u8be6\u7ec6\u8bb2\u89e3\uff1a
 https:\/\/www.csdn.net\/gather_27\/MtjaQg0sNjAxOTEtYmxvZwO0O0OO0O0O.html<\/a>
 RMQ\u7b97\u6cd5\u5206\u6790
 https:\/\/blog.csdn.net\/y990041769\/article\/details\/38405063<\/a><\/p>\n
ST\u7b97\u6cd5\u662f\u5c06\u8df3\u7684\u6b65\u6570\u52a0\u4ee5\u4e8c\u8fdb\u5236\u4f18\u5316\u3002
 LCA+ST\u500d\u589e+\u6811\u7684\u76f4\u5f84+\u5e76\u67e5\u96c6<\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nconst<\/span> int<\/span> maxn=<\/span>3e5<\/span>+<\/span>5<\/span>;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> to,<\/span>nex,<\/span>w;<\/span>\n}<\/span> road[<\/span>maxn*<\/span>2<\/span>]<\/span>;<\/span>\nstruct<\/span> nd\n{<\/span>\n    int<\/span> x;<\/span>\n    int<\/span> y;<\/span>\n}<\/span>;<\/span>\nnd qq[<\/span>maxn]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> n,<\/span>q,<\/span>cnt;<\/span>\nint<\/span> pre[<\/span>maxn]<\/span>[<\/span>32<\/span>]<\/span>,<\/span>head[<\/span>maxn]<\/span>,<\/span>depth[<\/span>maxn]<\/span>;<\/span>\nint<\/span> dis[<\/span>maxn]<\/span>;<\/span>\nll fa[<\/span>maxn]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>,<\/span>s[<\/span>maxn]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>,<\/span>t[<\/span>maxn]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nvoid<\/span> add<\/span>(<\/span>int<\/span> u,<\/span>int<\/span> v,<\/span>int<\/span> w)<\/span>\n{<\/span>\n    road[<\/span>cnt]<\/span>.<\/span>to=<\/span>v;<\/span>\n    road[<\/span>cnt]<\/span>.<\/span>w=<\/span>w;<\/span>\n    road[<\/span>cnt]<\/span>.<\/span>nex=<\/span>head[<\/span>u]<\/span>;<\/span>\n    head[<\/span>u]<\/span>=<\/span>cnt++<\/span>;<\/span>\n}<\/span>\nvoid<\/span> dfs<\/span>(<\/span>int<\/span> u,<\/span>int<\/span> fa)<\/span>\n{<\/span>\n    pre[<\/span>u]<\/span>[<\/span>0<\/span>]<\/span>=<\/span>fa;<\/span>\n    depth[<\/span>u]<\/span>=<\/span>depth[<\/span>fa]<\/span>+<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span> (<\/span>1<\/span><<<\/span>i)<\/span><=<\/span>depth[<\/span>u]<\/span>;<\/span> i++<\/span>)<\/span> \/\/\u500d\u589e<\/span>\n        pre[<\/span>u]<\/span>[<\/span>i]<\/span>=<\/span>pre[<\/span>pre[<\/span>u]<\/span>[<\/span>i-<\/span>1<\/span>]<\/span>]<\/span>[<\/span>i-<\/span>1<\/span>]<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>head[<\/span>u]<\/span>;<\/span> ~<\/span>i;<\/span> i=<\/span>road[<\/span>i]<\/span>.<\/span>nex)<\/span>\n    {<\/span>\n        int<\/span> v=<\/span>road[<\/span>i]<\/span>.<\/span>to;<\/span>\n        if<\/span>(<\/span>v!=<\/span>fa)<\/span>\n        {<\/span>\n            dis[<\/span>v]<\/span>=<\/span>dis[<\/span>u]<\/span>+<\/span>road[<\/span>i]<\/span>.<\/span>w;<\/span>\n            dfs<\/span>(<\/span>v,<\/span>u)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> lca<\/span>(<\/span>int<\/span> u,<\/span>int<\/span> v)<\/span>\n{<\/span>\n    if<\/span>(<\/span>depth[<\/span>u]<\/span><<\/span>depth[<\/span>v]<\/span>)<\/span>\n    {<\/span>\n        swap<\/span>(<\/span>u,<\/span>v)<\/span>;<\/span>\n    }<\/span>\n    int<\/span> i=<\/span>-<\/span>1<\/span>,<\/span>j;<\/span>\n    while<\/span>(<\/span>(<\/span>1<\/span><<<\/span>(<\/span>i+<\/span>1<\/span>)<\/span>)<\/span><=<\/span>depth[<\/span>u]<\/span>)<\/span>\n        i++<\/span>;<\/span>\n    for<\/span>(<\/span>j=<\/span>i;<\/span> j>=<\/span>0<\/span>;<\/span> j--<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>depth[<\/span>u]<\/span>-<\/span>(<\/span>1<\/span><<<\/span>j)<\/span>>=<\/span>depth[<\/span>v]<\/span>)<\/span>\n        {<\/span>\n            u=<\/span>pre[<\/span>u]<\/span>[<\/span>j]<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    if<\/span>(<\/span>u==<\/span>v)<\/span>\n        return<\/span> u;<\/span>\n    for<\/span>(<\/span>int<\/span> j=<\/span>i;<\/span> j>=<\/span>0<\/span>;<\/span> j--<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>pre[<\/span>u]<\/span>[<\/span>j]<\/span>!=<\/span>pre[<\/span>v]<\/span>[<\/span>j]<\/span>)<\/span>\n        {<\/span>\n            u=<\/span>pre[<\/span>u]<\/span>[<\/span>j]<\/span>;<\/span>\n            v=<\/span>pre[<\/span>v]<\/span>[<\/span>j]<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> pre[<\/span>u]<\/span>[<\/span>0<\/span>]<\/span>;<\/span>\n}<\/span>\nint<\/span> findfa<\/span>(<\/span>int<\/span> x)<\/span>\n{<\/span>\n    if<\/span>(<\/span>fa[<\/span>x]<\/span>!=<\/span>x)<\/span>\n        return<\/span> fa[<\/span>x]<\/span>=<\/span>findfa<\/span>(<\/span>fa[<\/span>x]<\/span>)<\/span>;<\/span>\n    else<\/span>\n        return<\/span> x;<\/span>\n}<\/span>\nint<\/span> cmp<\/span>(<\/span>ll &<\/span>x,<\/span>ll &<\/span>y,<\/span>int<\/span> &<\/span>z,<\/span>int<\/span> a,<\/span>int<\/span> b)<\/span>\n{<\/span>\n    int<\/span> dis1=<\/span>dis[<\/span>a]<\/span>+<\/span>dis[<\/span>b]<\/span>-<\/span>2<\/span>*<\/span>dis[<\/span>lca<\/span>(<\/span>a,<\/span>b)<\/span>]<\/span>;<\/span>\n    if<\/span>(<\/span>dis1><\/span>z)<\/span>\n    {<\/span>\n        z=<\/span>dis1;<\/span>\n        x=<\/span>a;<\/span>\n        y=<\/span>b;<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> solve<\/span>(<\/span>int<\/span> x,<\/span>int<\/span> y)<\/span>\n{<\/span>\n    int<\/span> fx=<\/span>findfa<\/span>(<\/span>x)<\/span>,<\/span>fy=<\/span>findfa<\/span>(<\/span>y)<\/span>;<\/span>\n    int<\/span> a=<\/span>s[<\/span>fx]<\/span>,<\/span>b=<\/span>t[<\/span>fx]<\/span>,<\/span>c=<\/span>s[<\/span>fy]<\/span>,<\/span>d=<\/span>t[<\/span>fy]<\/span>;<\/span>\n    fa[<\/span>fx]<\/span>=<\/span>fy;<\/span>\n    int<\/span> ans=<\/span>0<\/span>;<\/span>\n    cmp<\/span>(<\/span>s[<\/span>fy]<\/span>,<\/span>t[<\/span>fy]<\/span>,<\/span>ans,<\/span>a,<\/span>b)<\/span>;<\/span>\n    cmp<\/span>(<\/span>s[<\/span>fy]<\/span>,<\/span>t[<\/span>fy]<\/span>,<\/span>ans,<\/span>a,<\/span>c)<\/span>;<\/span>\n    cmp<\/span>(<\/span>s[<\/span>fy]<\/span>,<\/span>t[<\/span>fy]<\/span>,<\/span>ans,<\/span>a,<\/span>d)<\/span>;<\/span>\n    cmp<\/span>(<\/span>s[<\/span>fy]<\/span>,<\/span>t[<\/span>fy]<\/span>,<\/span>ans,<\/span>b,<\/span>c)<\/span>;<\/span>\n    cmp<\/span>(<\/span>s[<\/span>fy]<\/span>,<\/span>t[<\/span>fy]<\/span>,<\/span>ans,<\/span>b,<\/span>d)<\/span>;<\/span>\n    cmp<\/span>(<\/span>s[<\/span>fy]<\/span>,<\/span>t[<\/span>fy]<\/span>,<\/span>ans,<\/span>c,<\/span>d)<\/span>;<\/span>\n    return<\/span> ans;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>n)<\/span>;<\/span>\n    memset<\/span>(<\/span>head,<\/span>-<\/span>1<\/span>,<\/span>sizeof<\/span>(<\/span>head)<\/span>)<\/span>;<\/span>\n    memset<\/span>(<\/span>depth,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>depth)<\/span>)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        fa[<\/span>i]<\/span>=<\/span>s[<\/span>i]<\/span>=<\/span>t[<\/span>i]<\/span>=<\/span>i;<\/span>\n    cnt=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span> i<<\/span>n;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        int<\/span> u,<\/span>v,<\/span>w;<\/span>\n        scanf<\/span>(<\/span>\"%d %d\"<\/span>,<\/span>&<\/span>u,<\/span>&<\/span>v)<\/span>;<\/span>\n        w=<\/span>1<\/span>;<\/span>\n        qq[<\/span>i]<\/span>.<\/span>x=<\/span>u;<\/span>\n        qq[<\/span>i]<\/span>.<\/span>y=<\/span>v;<\/span>\n        add<\/span>(<\/span>u,<\/span>v,<\/span>w)<\/span>;<\/span>\n        add<\/span>(<\/span>v,<\/span>u,<\/span>w)<\/span>;<\/span>\n    }<\/span>\n    dis[<\/span>1<\/span>]<\/span>=<\/span>0<\/span>;<\/span>\n    dfs<\/span>(<\/span>1<\/span>,<\/span>0<\/span>)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        printf<\/span>(<\/span>\"%dn\"<\/span>,<\/span>solve<\/span>(<\/span>qq[<\/span>i]<\/span>.<\/span>x,<\/span>qq[<\/span>i]<\/span>.<\/span>y)<\/span>)<\/span>;<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/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":[],"class_list":["post-25","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/25","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=25"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/25\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=25"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=25"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=25"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}