{"id":42184,"date":"2025-06-06T18:25:53","date_gmt":"2025-06-06T10:25:53","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/42184.html"},"modified":"2025-06-06T18:25:53","modified_gmt":"2025-06-06T10:25:53","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e4%b8%8e%e7%ae%97%e6%b3%95%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0%ef%bc%88acwing-%e6%8f%90%e9%ab%98%e8%af%be%ef%bc%89-%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%c2%b7","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/42184.html","title":{"rendered":"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09----\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP"},"content":{"rendered":"

\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0—-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP<\/h2>\n

@@ author: \u660e\u6708\u6e05\u4e86\u4e2a\u98ce @@ first publish time: 2025.6.4<\/p>\n

ps\u2b50\ufe0f\u6811\u5f62\u52a8\u6001\u89c4\u5212（\u6811\u5f62DP）\u662f\u5904\u7406\u6811\u7ed3\u6784\u95ee\u9898\u7684\u4e00\u79cd\u52a8\u6001\u89c4\u5212\u65b9\u6cd5，\u7279\u5f81\u4e5f\u5f88\u660e\u663e，\u4f1a\u6709\u4e00\u4e2a\u6811\u5f62\u7ed3\u6784，\u5176\u5b9e\u662fDFS\u7684\u4f18\u5316\u3002<\/p>\n

Acwing 1072. \u6811\u7684\u6700\u957f\u8def\u5f84<\/h3>\n

\u7ed9\u5b9a\u4e00\u68f5\u6811，\u6811\u4e2d\u5305\u542b <\/p>\n

n <\/p>\n

n <\/p>\n

<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u4e2a\u8282\u70b9(\u7f16\u53f7 <\/p>\n

1 <\/p>\n

\u223c <\/p>\n

n <\/p>\n

1 \\\\sim n <\/p>\n

<\/span><\/span>1<\/span><\/span>\u223c<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>)\u548c <\/p>\n

n <\/p>\n

\u2212 <\/p>\n

1 <\/p>\n

n – 1 <\/p>\n

<\/span><\/span>n<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u6761\u65e0\u5411\u8fb9，\u6bcf\u6761\u8fb9\u90fd\u6709\u4e00\u4e2a\u6743\u503c\u3002<\/p>\n

\u73b0\u5728\u8bf7\u4f60\u627e\u5230\u6811\u4e2d\u6700\u957f\u7684\u4e00\u6761\u8def\u5f84\u3002<\/p>\n

\u6362\u53e5\u8bdd\u8bf4，\u8981\u627e\u5230\u4e24\u4e2a\u70b9，\u4f7f\u5f97\u4ed6\u4eec\u4e4b\u95f4\u7684\u8ddd\u79bb\u6700\u8fdc\u3002<\/p>\n

\u8f93\u5165\u683c\u5f0f<\/h4>\n

\u7b2c\u4e00\u884c\u5305\u542b\u6574\u6570 <\/p>\n

n <\/p>\n

n <\/p>\n

<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>，<\/p>\n

\u63a5\u4e0b\u6765 <\/p>\n

n <\/p>\n

\u2212 <\/p>\n

1 <\/p>\n

n – 1 <\/p>\n

<\/span><\/span>n<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u884c，\u6bcf\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570 <\/p>\n

a <\/p>\n

i <\/p>\n

, <\/p>\n

b <\/p>\n

i <\/p>\n

, <\/p>\n

c <\/p>\n

i <\/p>\n

a_i, b_i,c_i <\/p>\n

<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>c<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8868\u793a\u70b9 <\/p>\n

a <\/p>\n

i <\/p>\n

a_i <\/p>\n

<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u548c <\/p>\n

b <\/p>\n

i <\/p>\n

b_i <\/p>\n

<\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4\u5b58\u5728\u4e00\u6761\u6743\u503c\u4e3a <\/p>\n

c <\/p>\n

i <\/p>\n

c_i <\/p>\n

<\/span><\/span>c<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u7684\u8fb9\u3002<\/p>\n

\u8f93\u51fa\u683c\u5f0f<\/h4>\n

\u8f93\u51fa\u4e00\u4e2a\u6574\u6570，\u8868\u793a\u6811\u7684\u6700\u957f\u8def\u5f84\u7684\u957f\u5ea6\u3002<\/p>\n

\u6570\u636e\u8303\u56f4<\/h4>\n

<\/p>\n

1 <\/p>\n

\u2264 <\/p>\n

n <\/p>\n

\u2264 <\/p>\n

10000 <\/p>\n

1 \\\\le n \\\\le 10000 <\/p>\n

<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>n<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>10000<\/span><\/span><\/span><\/span><\/span>,<\/p>\n

<\/p>\n

1 <\/p>\n

\u2264 <\/p>\n

a <\/p>\n

i <\/p>\n

, <\/p>\n

b <\/p>\n

i <\/p>\n

\u2264 <\/p>\n

n <\/p>\n

1 \\\\le a_i,b_i \\\\le n <\/p>\n

<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2264<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>,<\/p>\n

<\/p>\n

1 <\/p>\n

\u2264 <\/p>\n

c <\/p>\n

i <\/p>\n

\u2264 <\/p>\n

10 <\/p>\n

5 <\/p>\n

1 \\\\le c_i \\\\le 10^5 <\/p>\n

<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>c<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2264<\/span><\/span><\/span><\/span>1<\/span>0<\/span><\/span>5<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

\u601d\u8def<\/h4>\n

\u627e\u6811\u7684\u6700\u957f\u8def\u5f84(\u76f4\u5f84)\u6709\u4e00\u4e2a\u901a\u7528\u7684\u601d\u8def：<\/p>\n

  • \u4efb\u9009\u4e00\u4e2a\u70b9，\u627e\u51fa\u79bb\u8fd9\u4e2a\u70b9\u6700\u8fdc\u7684\u70b9\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n

  • \u518d\u627e\u5230\u79bb\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u6700\u8fdc\u7684\u70b9 <\/p>\n

    v <\/p>\n

    v <\/p>\n

    <\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/li>\n

    <\/p>\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u4e0e <\/p>\n

    v <\/p>\n

    v <\/p>\n

    <\/span><\/span>v<\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4\u7684\u8def\u5f84\u5c31\u662f\u76f4\u5f84\u3002<\/p>\n

    \u8bc1\u660e\u5982\u4e0b；<\/p>\n

    \u5047\u8bbe\u4efb\u9009\u7684\u8fd9\u4e2a\u70b9\u662f <\/p>\n

    a <\/p>\n

    a <\/p>\n

    <\/span><\/span>a<\/span><\/span><\/span><\/span><\/span>，\u627e\u5230\u79bb\u4ed6\u6700\u8fdc\u7684\u70b9\u4e3a <\/p>\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>，\u53ea\u8981\u8bc1\u660e <\/p>\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u662f\u67d0\u6761\u76f4\u5f84\u7684\u4e00\u4e2a\u7aef\u70b9\u5c31\u884c\u4e86\u3002<\/p>\n

    \u5047\u8bbe\u4e00\u6761\u76f4\u5f84\u4e3a <\/p>\n

    b <\/p>\n

    c <\/p>\n

    bc <\/p>\n

    <\/span><\/span>b<\/span>c<\/span><\/span><\/span><\/span><\/span>，\u90a3\u4ed6\u53ef\u80fd\u4f1a\u4e0e <\/p>\n

    a <\/p>\n

    u <\/p>\n

    au <\/p>\n

    <\/span><\/span>a<\/span>u<\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4\u6ca1\u6709\u4ea4\u70b9，\u7531\u4e8e\u6811\u662f\u8fde\u901a\u7684，\u6240\u4ee5\u4ece <\/p>\n

    a <\/p>\n

    a <\/p>\n

    <\/span><\/span>a<\/span><\/span><\/span><\/span><\/span>\u5f00\u59cb\u8d70\u4e00\u5b9a\u80fd\u8d70\u5230 <\/p>\n

    c <\/p>\n

    c <\/p>\n

    <\/span><\/span>c<\/span><\/span><\/span><\/span><\/span>\u70b9，\u5047\u8bbe\u8fd9\u6761\u8def\u5f84\u662f <\/p>\n

    a <\/p>\n

    x <\/p>\n

    y <\/p>\n

    c <\/p>\n

    axyc <\/p>\n

    <\/span><\/span>a<\/span>x<\/span>yc<\/span><\/span><\/span><\/span><\/span>，\u5176\u4e2d <\/p>\n

    x <\/p>\n

    x <\/p>\n

    <\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>\u5728 <\/p>\n

    a <\/p>\n

    u <\/p>\n

    au <\/p>\n

    <\/span><\/span>a<\/span>u<\/span><\/span><\/span><\/span><\/span>\u4e0a， <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>\u5728 <\/p>\n

    b <\/p>\n

    c <\/p>\n

    bc <\/p>\n

    <\/span><\/span>b<\/span>c<\/span><\/span><\/span><\/span><\/span>\u4e0a，\u7531\u4e8e <\/p>\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u662f\u79bb <\/p>\n

    a <\/p>\n

    a <\/p>\n

    <\/span><\/span>a<\/span><\/span><\/span><\/span><\/span>\u6700\u8fdc\u7684\u70b9，\u90a3\u4e48 <\/p>\n

    x <\/p>\n

    u <\/p>\n

    xu <\/p>\n

    <\/span><\/span>xu<\/span><\/span><\/span><\/span><\/span>\u7684\u957f\u5ea6\u5927\u4e8e\u7b49\u4e8e <\/p>\n

    x <\/p>\n

    y <\/p>\n

    + <\/p>\n

    y <\/p>\n

    c <\/p>\n

    xy + yc <\/p>\n

    <\/span><\/span>x<\/span>y<\/span><\/span>+<\/span><\/span><\/span><\/span>yc<\/span><\/span><\/span><\/span><\/span>，\u90a3\u4e48\u5c31\u6709 <\/p>\n

    b <\/p>\n

    y <\/p>\n

    + <\/p>\n

    y <\/p>\n

    x <\/p>\n

    + <\/p>\n

    x <\/p>\n

    u <\/p>\n

    \u2265 <\/p>\n

    y <\/p>\n

    c <\/p>\n

    by + yx + xu \\\\ge yc <\/p>\n

    <\/span><\/span>b<\/span>y<\/span><\/span>+<\/span><\/span><\/span><\/span>y<\/span>x<\/span><\/span>+<\/span><\/span><\/span><\/span>xu<\/span><\/span>\u2265<\/span><\/span><\/span><\/span>yc<\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64 <\/p>\n

    b <\/p>\n

    u <\/p>\n

    bu <\/p>\n

    <\/span><\/span>b<\/span>u<\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4\u7684\u8ddd\u79bb\u4e00\u5b9a\u5927\u4e8e\u7b49\u4e8e <\/p>\n

    b <\/p>\n

    c <\/p>\n

    bc <\/p>\n

    <\/span><\/span>b<\/span>c<\/span><\/span><\/span><\/span><\/span>\u7684\u957f\u5ea6，\u56e0\u6b64 <\/p>\n

    b <\/p>\n

    u <\/p>\n

    bu <\/p>\n

    <\/span><\/span>b<\/span>u<\/span><\/span><\/span><\/span><\/span>\u4e00\u5b9a\u662f\u4e00\u6761\u76f4\u5f84\u7684\u7aef\u70b9\u3002<\/p>\n

    \u53e6\u4e00\u79cd\u60c5\u51b5\u662f\u4e24\u6761\u7ebf\u76f8\u4ea4，\u5047\u8bbe\u4ea4\u70b9\u662f <\/p>\n

    x <\/p>\n

    x <\/p>\n

    <\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>，\u90a3\u4e48\u7531\u4e8e <\/p>\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u662f\u79bb <\/p>\n

    a <\/p>\n

    a <\/p>\n

    <\/span><\/span>a<\/span><\/span><\/span><\/span><\/span>\u6700\u8fdc\u7684\u70b9，\u5c31\u6709 <\/p>\n

    u <\/p>\n

    x <\/p>\n

    \u2265 <\/p>\n

    x <\/p>\n

    c <\/p>\n

    ux \\\\ge xc <\/p>\n

    <\/span><\/span>ux<\/span><\/span>\u2265<\/span><\/span><\/span><\/span>x<\/span>c<\/span><\/span><\/span><\/span><\/span>，\u90a3\u4e48 <\/p>\n

    b <\/p>\n

    x <\/p>\n

    + <\/p>\n

    x <\/p>\n

    u <\/p>\n

    \u2265 <\/p>\n

    b <\/p>\n

    c <\/p>\n

    bx + xu \\\\ge bc <\/p>\n

    <\/span><\/span>b<\/span>x<\/span><\/span>+<\/span><\/span><\/span><\/span>xu<\/span><\/span>\u2265<\/span><\/span><\/span><\/span>b<\/span>c<\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64 <\/p>\n

    u <\/p>\n

    u <\/p>\n

    <\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>\u4e5f\u4e00\u5b9a\u662f\u4e00\u6761\u76f4\u5f84\u7684\u7aef\u70b9\u3002<\/p>\n

    \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

    \u7531\u4e8e\u8fd9\u9053\u9898\u76ee\u5e76\u6ca1\u6709\u6307\u5b9a\u6839\u8282\u70b9，\u56e0\u6b64\u53ef\u4ee5\u4efb\u9009\u4e00\u4e2a\u70b9\u5c06\u6574\u68f5\u6811\u6784\u5efa\u8d77\u6765，\u7136\u540e\u5bf9\u4e8e\u6bcf\u4e2a\u70b9\u8bb0\u5f55\u7ecf\u8fc7\u8be5\u70b9\u7684\u6700\u957f\u8def\u5f84\u3002<\/p>\n

    \u5bf9\u4e8e\u4e00\u4e2a\u70b9\u7684\u6700\u957f\u8def\u5f84，\u5bf9\u4e8e\u6bcf\u4e2a\u70b9\u6765\u8bf4\u53ef\u4ee5\u5206\u4e3a\u4e24\u79cd\u60c5\u51b5，\u4e00\u79cd\u662f\u5f80\u4e0b\u8d70，\u4e00\u79cd\u662f\u5f80\u4e0a\u8d70\u3002\u5c31\u662f\u679a\u4e3e\u4ed6\u7684\u6bcf\u4e2a\u5b50\u8282\u70b9\u5b58\u7684\u6700\u5927\u8ddd\u79bb\u518d\u52a0\u4e0a\u4ed6\u5230\u8fd9\u4e2a\u5b50\u8282\u70b9\u7684\u8ddd\u79bb；\u53e6\u4e00\u79cd\u60c5\u51b5\u662f\u7a7f\u8fc7\u4e00\u4e2a\u70b9\u7684\u8def\u5f84，\u90a3\u4e48\u5c31\u53ef\u4ee5\u8ba1\u7b97\u8fd9\u4e2a\u70b9\u5f80\u4e0b\u7684\u6700\u957f\u7684\u8def\u5f84\u4ee5\u53ca\u7b2c\u4e8c\u957f\u7684\u8def\u5f84\u76f8\u52a0\u3002<\/p>\n

    \u4ee3\u7801<\/h4>\n

    #<\/span>include<\/span> <iostream><\/span><\/span>
    \n#<\/span>include<\/span> <cstring><\/span><\/span>
    \n#<\/span>include<\/span> <cstdio><\/span><\/span>
    \n#<\/span>include<\/span> <algorithm><\/span><\/span><\/p>\n

    using<\/span> namespace<\/span> std;<\/span><\/p>\n

    const<\/span> int<\/span> N =<\/span> 10010<\/span>,<\/span> M =<\/span> N *<\/span> 2<\/span>;<\/span><\/p>\n

    int<\/span> n;<\/span>
    \nint<\/span> h[<\/span>N]<\/span>,<\/span> e[<\/span>M]<\/span>,<\/span> ne[<\/span>M]<\/span>,<\/span> w[<\/span>M]<\/span>,<\/span> idx;<\/span>
    \nint<\/span> ans;<\/span><\/p>\n

    void<\/span> add<\/span>(<\/span>int<\/span> a,<\/span> int<\/span> b,<\/span> int<\/span> c)<\/span>
    \n{<\/span>
    \n w[<\/span>idx]<\/span> =<\/span> c,<\/span> e[<\/span>idx]<\/span> =<\/span> b,<\/span> ne[<\/span>idx]<\/span> =<\/span> h[<\/span>a]<\/span>,<\/span> h[<\/span>a]<\/span> =<\/span> idx ++<\/span>;<\/span>
    \n}<\/span><\/p>\n

    int<\/span> dfs<\/span>(<\/span>int<\/span> u,<\/span> int<\/span> father)<\/span>
    \n{<\/span>
    \n int<\/span> dist =<\/span> 0<\/span>;<\/span>
    \n int<\/span> d1 =<\/span> 0<\/span>,<\/span> d2 =<\/span> 0<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span>
    \n if<\/span>(<\/span>j ==<\/span> father)<\/span> continue<\/span>;<\/span><\/p>\n

    int<\/span> d =<\/span> dfs<\/span>(<\/span>j,<\/span> u)<\/span> +<\/span> w[<\/span>i]<\/span>;<\/span>
    \n dist =<\/span> max<\/span>(<\/span>dist,<\/span> d)<\/span>;<\/span><\/p>\n

    if<\/span>(<\/span>d >=<\/span> d1)<\/span>
    \n {<\/span>
    \n d2 =<\/span> d1;<\/span>
    \n d1 =<\/span> d;<\/span>
    \n }<\/span> else<\/span> if<\/span>(<\/span>d ><\/span> d2)<\/span> d2 =<\/span> d;<\/span>
    \n }<\/span><\/p>\n

    ans =<\/span> max<\/span>(<\/span>ans,<\/span> d1 +<\/span> d2)<\/span>;<\/span>
    \n return<\/span> dist;<\/span>
    \n}<\/span><\/p>\n

    int<\/span> main<\/span>(<\/span>)<\/span>
    \n{<\/span>
    \n cin >><\/span> n;<\/span><\/p>\n

    memset<\/span>(<\/span>h,<\/span> –<\/span>1<\/span>,<\/span> sizeof<\/span> h)<\/span>;<\/span>
    \n for<\/span>(<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n –<\/span> 1<\/span>;<\/span> i ++<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> a,<\/span> b,<\/span> c;<\/span>
    \n cin >><\/span> a >><\/span> b >><\/span> c;<\/span>
    \n add<\/span>(<\/span>a,<\/span> b,<\/span> c)<\/span>,<\/span> add<\/span>(<\/span>b,<\/span> a,<\/span> c)<\/span>;<\/span>
    \n }<\/span><\/p>\n

    dfs<\/span>(<\/span>1<\/span>,<\/span> –<\/span>1<\/span>)<\/span>;<\/span><\/p>\n

    cout <<<\/span> ans <<<\/span> endl;<\/span><\/p>\n

    return<\/span> 0<\/span>;<\/span>
    \n}<\/span><\/p>\n

    Acwing 1073. \u6811\u7684\u4e2d\u5fc3<\/h3>\n

    \u7ed9\u5b9a\u4e00\u68f5\u6811，\u6811\u4e2d\u5305\u542b <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u4e2a\u8282\u70b9(\u7f16\u53f7 <\/p>\n

    1 <\/p>\n

    \u223c <\/p>\n

    n <\/p>\n

    1 \\\\sim n <\/p>\n

    <\/span><\/span>1<\/span><\/span>\u223c<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>)\u548c <\/p>\n

    n <\/p>\n

    \u2212 <\/p>\n

    1 <\/p>\n

    n – 1 <\/p>\n

    <\/span><\/span>n<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u6761\u65e0\u5411\u8fb9，\u6bcf\u6761\u8fb9\u90fd\u6709\u4e00\u4e2a\u6743\u503c\u3002<\/p>\n

    \u8bf7\u4f60\u5728\u6811\u4e2d\u627e\u5230\u4e00\u4e2a\u70b9，\u4f7f\u5f97\u8be5\u70b9\u5230\u6811\u4e2d\u5176\u4ed6\u7ed3\u70b9\u7684\u6700\u8fdc\u8ddd\u79bb\u6700\u8fd1\u3002<\/p>\n

    \u8f93\u5165\u683c\u5f0f<\/h4>\n

    \u7b2c\u4e00\u884c\u5305\u542b\u6574\u6570 <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>，<\/p>\n

    \u63a5\u4e0b\u6765 <\/p>\n

    n <\/p>\n

    \u2212 <\/p>\n

    1 <\/p>\n

    n – 1 <\/p>\n

    <\/span><\/span>n<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u884c，\u6bcf\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570 <\/p>\n

    a <\/p>\n

    i <\/p>\n

    , <\/p>\n

    b <\/p>\n

    i <\/p>\n

    , <\/p>\n

    c <\/p>\n

    i <\/p>\n

    a_i, b_i,c_i <\/p>\n

    <\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>c<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8868\u793a\u70b9 <\/p>\n

    a <\/p>\n

    i <\/p>\n

    a_i <\/p>\n

    <\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u548c <\/p>\n

    b <\/p>\n

    i <\/p>\n

    b_i <\/p>\n

    <\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4\u5b58\u5728\u4e00\u6761\u6743\u503c\u4e3a <\/p>\n

    c <\/p>\n

    i <\/p>\n

    c_i <\/p>\n

    <\/span><\/span>c<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u7684\u8fb9\u3002<\/p>\n

    \u8f93\u51fa\u683c\u5f0f<\/h4>\n

    \u8f93\u51fa\u4e00\u4e2a\u6574\u6570，\u8868\u793a\u6240\u6c42\u70b9\u5230\u6811\u4e2d\u5176\u4ed6\u7ed3\u70b9\u7684\u6700\u8fdc\u8ddd\u79bb\u3002<\/p>\n

    \u6570\u636e\u8303\u56f4<\/h4>\n

    <\/p>\n

    1 <\/p>\n

    \u2264 <\/p>\n

    n <\/p>\n

    \u2264 <\/p>\n

    10000 <\/p>\n

    1 \\\\le n \\\\le 10000 <\/p>\n

    <\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>n<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>10000<\/span><\/span><\/span><\/span><\/span>,<\/p>\n

    <\/p>\n

    1 <\/p>\n

    \u2264 <\/p>\n

    a <\/p>\n

    i <\/p>\n

    , <\/p>\n

    b <\/p>\n

    i <\/p>\n

    \u2264 <\/p>\n

    n <\/p>\n

    1 \\\\le a_i,b_i \\\\le n <\/p>\n

    <\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2264<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>,<\/p>\n

    <\/p>\n

    1 <\/p>\n

    \u2264 <\/p>\n

    c <\/p>\n

    i <\/p>\n

    \u2264 <\/p>\n

    10 <\/p>\n

    5 <\/p>\n

    1 \\\\le c_i \\\\le 10^5 <\/p>\n

    <\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>c<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2264<\/span><\/span><\/span><\/span>1<\/span>0<\/span><\/span>5<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u601d\u8def<\/h4>\n

    \u4e0e\u4e0a\u4e00\u9898\u4e00\u6837，\u5bf9\u4e8e\u6811\u4e2d\u7684\u4e00\u70b9\u6709\u5411\u4e0a\u8d70\u4e0e\u5411\u4e0b\u8d70\u4e24\u79cd\u65b9\u6848，\u6bcf\u4e2a\u70b9\u90fd\u8bb0\u5f55\u4e00\u4e2a\u5411\u4e0a\u8d70\u4e0e\u5411\u4e0b\u8d70\u7684\u6700\u5927\u503c，\u5047\u8bbe\u70b9 <\/p>\n

    2 <\/p>\n

    2 <\/p>\n

    <\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u5411\u5176\u7236\u8282\u70b9 <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u8d70，\u90a3\u4e48\u8fd9\u5c31\u662f\u5411\u4e0a\u8d70，\u5728 <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u70b9\u53ef\u4ee5\u7ee7\u7eed\u5411\u4e0a\u8d70，\u4e5f\u53ef\u4ee5\u5411\u4e0b\u4e0d\u7ecf\u8fc7\u70b9 <\/p>\n

    2 <\/p>\n

    2 <\/p>\n

    <\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u7684\u5b50\u8282\u70b9\u8d70，\u82e5\u5411\u4e0b\u8d70，\u90a3\u5c31\u8981\u8003\u8651\u70b9 <\/p>\n

    2 <\/p>\n

    2 <\/p>\n

    <\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u662f\u5426\u662f\u5411\u4e0b\u8d70\u7684\u6700\u5927\u957f\u5ea6，\u5982\u679c\u662f，\u90a3\u5c31\u4f7f\u80fd\u9009\u62e9\u6b21\u5927\u503c\u66f4\u65b0\u3002<\/p>\n

    \u8fd9\u4e00\u9898\u590d\u6742\u7684\u5730\u65b9\u5728\u4e8e，\u66f4\u65b0\u7684\u8fc7\u7a0b\u540c\u65f6\u7528\u5230\u4e86\u5b50\u8282\u70b9\u66f4\u65b0\u7236\u8282\u70b9\u548c\u7236\u8282\u70b9\u66f4\u65b0\u5b50\u8282\u70b9\u3002<\/p>\n

    \u4ee3\u7801<\/h4>\n

    #<\/span>include<\/span> <iostream><\/span><\/span>
    \n#<\/span>include<\/span> <cstring><\/span><\/span>
    \n#<\/span>include<\/span> <cstdio><\/span><\/span>
    \n#<\/span>include<\/span> <algorithm><\/span><\/span><\/p>\n

    using<\/span> namespace<\/span> std;<\/span><\/p>\n

    const<\/span> int<\/span> N =<\/span> 100010<\/span>,<\/span> M =<\/span> N *<\/span> 2<\/span>,<\/span> inf =<\/span> 0x3f3f3f3f<\/span>;<\/span><\/p>\n

    int<\/span> n;<\/span>
    \nint<\/span> h[<\/span>N]<\/span>,<\/span> e[<\/span>M]<\/span> ,<\/span>w[<\/span>M]<\/span>,<\/span> ne[<\/span>M]<\/span>,<\/span> idx;<\/span>
    \nint<\/span> d1[<\/span>N]<\/span>,<\/span> d2[<\/span>N]<\/span>,<\/span> up[<\/span>N]<\/span>;<\/span>
    \nint<\/span> p1[<\/span>N]<\/span>,<\/span> p2[<\/span>N]<\/span>;<\/span><\/p>\n

    void<\/span> add<\/span>(<\/span>int<\/span> a,<\/span> int<\/span> b,<\/span> int<\/span> c)<\/span>
    \n{<\/span>
    \n e[<\/span>idx]<\/span> =<\/span> b,<\/span> w[<\/span>idx]<\/span> =<\/span> c,<\/span> ne[<\/span>idx]<\/span> =<\/span> h[<\/span>a]<\/span>,<\/span> h[<\/span>a]<\/span> =<\/span> idx ++<\/span>;<\/span>
    \n}<\/span><\/p>\n

    int<\/span> dfs_d<\/span>(<\/span>int<\/span> u,<\/span> int<\/span> father)<\/span>
    \n{<\/span>
    \n if<\/span>(<\/span>h[<\/span>u]<\/span> ==<\/span> –<\/span>1<\/span>)<\/span> return<\/span> 0<\/span>;<\/span><\/p>\n

    d1[<\/span>u]<\/span> =<\/span> d2[<\/span>u]<\/span> =<\/span> –<\/span>inf;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span>
    \n if<\/span>(<\/span>j ==<\/span> father)<\/span> continue<\/span>;<\/span>
    \n int<\/span> d =<\/span> dfs_d<\/span>(<\/span>j,<\/span> u)<\/span> +<\/span> w[<\/span>i]<\/span>;<\/span>
    \n if<\/span>(<\/span>d >=<\/span> d1[<\/span>u]<\/span>)<\/span>
    \n {<\/span>
    \n d2[<\/span>u]<\/span> =<\/span> d1[<\/span>u]<\/span>,<\/span> d1[<\/span>u]<\/span> =<\/span> d;<\/span>
    \n p2[<\/span>u]<\/span> =<\/span> p1[<\/span>u]<\/span>,<\/span> p1[<\/span>u]<\/span> =<\/span> j;<\/span> \/\/ \u8bb0\u5f55\u6700\u5927\u503c\u548c\u6b21\u5927\u503c\u662f\u4ece\u5411\u54ea\u4e2a\u5b50\u8282\u70b9\u8d70\u7684<\/span>
    \n }<\/span> else<\/span> if<\/span>(<\/span>d ><\/span> d2[<\/span>u]<\/span>)<\/span>
    \n d2[<\/span>u]<\/span> =<\/span> d,<\/span> p2[<\/span>u]<\/span> =<\/span> j;<\/span>
    \n }<\/span><\/p>\n

    if<\/span>(<\/span>d1[<\/span>u]<\/span> ==<\/span> –<\/span>inf)<\/span> d1[<\/span>u]<\/span> =<\/span> d2[<\/span>u]<\/span> =<\/span> 0<\/span>;<\/span> \/\/ \u5982\u679c\u662f\u53f6\u5b50\u7ed3\u70b9\u65e0\u6cd5\u5f80\u4e0b，\u7f6e\u4e3a0<\/span><\/p>\n

    return<\/span> d1[<\/span>u]<\/span>;<\/span>
    \n}<\/span><\/p>\n

    int<\/span> dfs_u<\/span>(<\/span>int<\/span> u,<\/span> int<\/span> father)<\/span>
    \n{<\/span>
    \n if<\/span>(<\/span>h[<\/span>u]<\/span> ==<\/span> –<\/span>1<\/span>)<\/span> return<\/span> 0<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span>
    \n if<\/span>(<\/span>j ==<\/span> father)<\/span> continue<\/span>;<\/span><\/p>\n

    if<\/span>(<\/span>p1[<\/span>u]<\/span> ==<\/span> j)<\/span> up[<\/span>j]<\/span> =<\/span> max<\/span>(<\/span>up[<\/span>u]<\/span>,<\/span> d2[<\/span>u]<\/span>)<\/span> +<\/span> w[<\/span>i]<\/span>;<\/span>
    \n else<\/span> up[<\/span>j]<\/span> =<\/span> max<\/span>(<\/span>up[<\/span>u]<\/span>,<\/span> d1[<\/span>u]<\/span>)<\/span> +<\/span> w[<\/span>i]<\/span>;<\/span><\/p>\n

    dfs_u<\/span>(<\/span>j,<\/span> u)<\/span>;<\/span>
    \n }<\/span>
    \n}<\/span><\/p>\n

    int<\/span> main<\/span>(<\/span>)<\/span>
    \n{<\/span>
    \n cin >><\/span> n;<\/span><\/p>\n

    memset<\/span>(<\/span>h,<\/span> –<\/span>1<\/span>,<\/span> sizeof<\/span> h)<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n –<\/span> 1<\/span>;<\/span> i ++<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> a,<\/span> b,<\/span> c;<\/span>
    \n cin >><\/span> a >><\/span> b >><\/span> c;<\/span>
    \n add<\/span>(<\/span>a,<\/span> b,<\/span> c)<\/span>,<\/span> add<\/span>(<\/span>b,<\/span> a,<\/span> c)<\/span>;<\/span>
    \n }<\/span><\/p>\n

    dfs_d<\/span>(<\/span>1<\/span>,<\/span> –<\/span>1<\/span>)<\/span>;<\/span>
    \n dfs_u<\/span>(<\/span>1<\/span>,<\/span> –<\/span>1<\/span>)<\/span>;<\/span><\/p>\n

    int<\/span> res =<\/span> inf;<\/span>
    \n for<\/span>(<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <=<\/span> n;<\/span> i ++<\/span>)<\/span> res =<\/span> min<\/span>(<\/span>res,<\/span> max<\/span>(<\/span>up[<\/span>i]<\/span>,<\/span> d1[<\/span>i]<\/span>)<\/span>)<\/span>;<\/span><\/p>\n

    cout <<<\/span> res <<<\/span> endl;<\/span><\/p>\n

    return<\/span> 0<\/span>;<\/span><\/p>\n

    }<\/span><\/p>\n

    Acwing 1075. \u6570\u5b57\u8f6c\u6362<\/h3>\n

    \u5982\u679c\u4e00\u4e2a\u6570 <\/p>\n

    x <\/p>\n

    x <\/p>\n

    <\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>\u7684\u7ea6\u6570\u4e4b\u548c <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>(\u4e0d\u5305\u62ec\u4ed6\u672c\u8eab)\u6bd4\u4ed6\u672c\u8eab\u5c0f，\u90a3\u4e48 <\/p>\n

    x <\/p>\n

    \u53ef\u4ee5\u53d8\u6210 <\/p>\n

    x\u53ef\u4ee5\u53d8\u6210 <\/p>\n

    <\/span><\/span>x<\/span>\u53ef\u4ee5\u53d8\u6210<\/span><\/span><\/span><\/span><\/span> <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>， <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>\u4e5f\u53ef\u4ee5\u53d8\u6210 <\/p>\n

    x <\/p>\n

    x <\/p>\n

    <\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u4f8b\u5982 <\/p>\n

    4 <\/p>\n

    4 <\/p>\n

    <\/span><\/span>4<\/span><\/span><\/span><\/span><\/span>\u53ef\u4ee5\u53d8\u6210 <\/p>\n

    3 <\/p>\n

    3 <\/p>\n

    <\/span><\/span>3<\/span><\/span><\/span><\/span><\/span>， <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u53ef\u4ee5\u53d8\u6210 <\/p>\n

    7 <\/p>\n

    7 <\/p>\n

    <\/span><\/span>7<\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u9650\u5236\u6240\u6709\u6570\u5b57\u53d8\u6362\u5728\u4e0d\u8d85\u8fc7 <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u7684\u6b63\u6574\u6570\u8303\u56f4\u5185\u8fdb\u884c，\u6c42\u4e0d\u65ad\u8fdb\u884c\u6570\u5b57\u53d8\u6362\u4e14\u4e0d\u51fa\u73b0\u91cd\u590d\u6570\u5b57\u7684\u6700\u591a\u53d8\u6362\u6b65\u6570\u3002<\/p>\n

    \u8f93\u5165\u683c\u5f0f<\/h4>\n

    \u8f93\u5165\u4e00\u4e2a\u6b63\u6574\u6570 <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u8f93\u51fa\u683c\u5f0f<\/h4>\n

    \u8f93\u51fa\u65ad\u8fdb\u884c\u6570\u5b57\u53d8\u6362\u4e14\u4e0d\u51fa\u73b0\u91cd\u590d\u6570\u5b57\u7684\u6700\u591a\u53d8\u6362\u6b65\u6570<\/p>\n

    \u6570\u636e\u8303\u56f4<\/h4>\n

    <\/p>\n

    1 <\/p>\n

    \u2264 <\/p>\n

    n <\/p>\n

    \u2264 <\/p>\n

    50000 <\/p>\n

    1 \\\\le n \\\\le 50000 <\/p>\n

    <\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>n<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>50000<\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u601d\u8def<\/h4>\n

    \u5bf9\u4e8e\u6bcf\u4e2a\u6570 <\/p>\n

    x <\/p>\n

    x <\/p>\n

    <\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>\u90fd\u4f1a\u6709\u4e00\u4e2a\u7ea6\u6570\u4e4b\u548c <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>\u4e0e\u4e4b\u5bf9\u5e94，\u4e14 <\/p>\n

    x <\/p>\n

    x <\/p>\n

    <\/span><\/span>x<\/span><\/span><\/span><\/span><\/span>\u5230 <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>\u7684\u5173\u7cfb\u662f\u552f\u4e00\u7684，\u4f46\u9700\u8981\u6ce8\u610f\u7684\u662f <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>\u53ef\u80fd\u4f1a\u5bf9\u5e94\u4e8e\u591a\u4e2a\u6570，\u56e0\u6b64\u8981\u5c06 <\/p>\n

    y <\/p>\n

    y <\/p>\n

    <\/span><\/span>y<\/span><\/span><\/span><\/span><\/span>\u4f5c\u4e3a\u7236\u8282\u70b9\u3002\u90a3\u4e48\u5bf9\u4e8e\u6240\u6709\u6570\u5c31\u53ef\u4ee5\u6784\u5efa\u51fa\u4e00\u5806\u6811(\u6ce8\u610f\u4e0d\u662f\u4e00\u68f5\u6811，\u56e0\u4e3a\u4e0d\u4e00\u5b9a\u6240\u6709\u6570\u90fd\u80fd\u8fde\u901a)，\u6700\u591a\u53d8\u6362\u6b65\u6570\u5c31\u662f\u8fd9\u5806\u6811\u4e2d\u6700\u957f\u7684\u6811\u7684\u76f4\u5f84，\u5c31\u662f\u4e0a\u9762\u7684\u7b2c\u4e00\u9898\u3002<\/p>\n

    \u95ee\u9898\u5c31\u662f\u5efa\u6811，\u4e5f\u5c31\u662f\u627e\u5230 <\/p>\n

    1 <\/p>\n

    \u223c <\/p>\n

    n <\/p>\n

    1 \\\\sim n <\/p>\n

    <\/span><\/span>1<\/span><\/span>\u223c<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u4e2d\u6240\u6709\u6570\u7684\u7ea6\u6570\u4e4b\u548c\u3002\u5f53\u7136\u53ef\u4ee5\u679a\u4e3e\u6bcf\u4e2a\u6570\u8fdb\u884c\u8ba1\u7b97（\u8bd5\u9664\u6cd5），\u4f46\u662f\u5982\u679c <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u7684\u8303\u56f4\u8fdb\u4e00\u6b65\u6269\u5927\u5c31\u4f1a\u8d85\u65f6\u3002\u53ef\u4ee5\u53cd\u5411\u601d\u8003，\u4e0d\u662f\u6c42\u6bcf\u4e2a\u6570\u7684\u7ea6\u6570\u662f\u54ea\u4e9b\u6570，\u800c\u662f\u6c42\u6bcf\u4e2a\u6570\u662f\u54ea\u4e9b\u6570\u7684\u7ea6\u6570，\u4e5f\u5c31\u662f\u679a\u4e3e\u6bcf\u4e2a\u6570\u7684\u500d\u6570<\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <=<\/span> n;<\/span> i ++<\/span>)<\/span>
    \n for<\/span>(<\/span>int<\/span> j =<\/span> 2<\/span>;<\/span> j *<\/span> i <=<\/span> n;<\/span> j ++<\/span>)<\/span> \/\/ \u4ece2\u5f00\u59cb\u679a\u4e3e<\/span><\/p>\n

    \u8fd9\u6837\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f <\/p>\n

    n <\/p>\n

    ln <\/p>\n

    \u2061 <\/p>\n

    n <\/p>\n

    n \\\\ln{n} <\/p>\n

    <\/span><\/span>n<\/span><\/span>ln<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span><\/span>，\u56e0\u4e3a <\/p>\n

    n <\/p>\n

    + <\/p>\n

    n <\/p>\n

    2 <\/p>\n

    + <\/p>\n

    n <\/p>\n

    3 <\/p>\n

    + <\/p>\n

    \u22ef <\/p>\n

    n + \\\\frac{n}{2} + \\\\frac{n}{3} + \\\\cdots <\/p>\n

    <\/span><\/span>n<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>3<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>\u22ef<\/span><\/span><\/span><\/span><\/span>\u662f\u4e00\u4e2a\u8c03\u548c\u7ea7\u6570，<\/p>\n

    \u4ee3\u7801<\/h4>\n

    #<\/span>include<\/span> <iostream><\/span><\/span>
    \n#<\/span>include<\/span> <cstring><\/span><\/span>
    \n#<\/span>include<\/span> <cstdio><\/span><\/span>
    \n#<\/span>include<\/span> <algorithm><\/span><\/span><\/p>\n

    using<\/span> namespace<\/span> std;<\/span><\/p>\n

    const<\/span> int<\/span> N =<\/span> 50010<\/span>;<\/span><\/p>\n

    int<\/span> n;<\/span>
    \nint<\/span> sum[<\/span>N]<\/span>;<\/span>
    \nint<\/span> h[<\/span>N]<\/span>,<\/span> e[<\/span>N]<\/span>,<\/span> ne[<\/span>N]<\/span>,<\/span> idx;<\/span>
    \nbool<\/span> st[<\/span>N]<\/span>;<\/span>
    \nint<\/span> ans;<\/span><\/p>\n

    void<\/span> add<\/span>(<\/span>int<\/span> a,<\/span> int<\/span> b)<\/span>
    \n{<\/span>
    \n e[<\/span>idx]<\/span> =<\/span> b,<\/span> ne[<\/span>idx]<\/span> =<\/span> h[<\/span>a]<\/span>,<\/span> h[<\/span>a]<\/span> =<\/span> idx ++<\/span>;<\/span>
    \n}<\/span><\/p>\n

    int<\/span> dfs<\/span>(<\/span>int<\/span> u)<\/span>
    \n{<\/span>
    \n int<\/span> d1 =<\/span> 0<\/span>,<\/span> d2 =<\/span> 0<\/span>;<\/span>
    \n for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span>
    \n int<\/span> d =<\/span> dfs<\/span>(<\/span>j)<\/span> +<\/span> 1<\/span>;<\/span>
    \n if<\/span>(<\/span>d >=<\/span> d1)<\/span> d2 =<\/span> d1,<\/span> d1 =<\/span> d;<\/span>
    \n else<\/span> if<\/span>(<\/span>d ><\/span> d2)<\/span> d2 =<\/span> d;<\/span>
    \n }<\/span><\/p>\n

    ans =<\/span> max<\/span>(<\/span>ans,<\/span> d1 +<\/span> d2)<\/span>;<\/span>
    \n return<\/span> d1;<\/span>
    \n}<\/span><\/p>\n

    int<\/span> main<\/span>(<\/span>)<\/span>
    \n{<\/span>
    \n cin >><\/span> n;<\/span><\/p>\n

    memset<\/span>(<\/span>h,<\/span> –<\/span>1<\/span>,<\/span> sizeof<\/span> h)<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <=<\/span>n;<\/span> i ++<\/span>)<\/span>
    \n for<\/span>(<\/span>int<\/span> j =<\/span> 2<\/span>;<\/span> j <=<\/span> n \/<\/span> i;<\/span> j ++<\/span>)<\/span>
    \n sum[<\/span>i *<\/span> j]<\/span> +=<\/span> i;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> 2<\/span>;<\/span> i <=<\/span> n;<\/span> i ++<\/span>)<\/span> \/\/ \u5efa\u7acb\u8fb9\u7684\u65f6\u5019\u8981\u4ece2\u5f00\u59cb，\u56e0\u4e3a\u5bf9\u4e8e1\u6765\u8bf4，\u4ed6\u4f1a\u548c0\u5efa\u8fb9，\u9898\u76ee\u8981\u6c42\u662f\u6b63\u6574\u6570\u3002<\/span>
    \n if<\/span>(<\/span>sum[<\/span>i]<\/span> <<\/span> i)<\/span>
    \n {<\/span>
    \n add<\/span>(<\/span>sum[<\/span>i]<\/span>,<\/span> i)<\/span>;<\/span>
    \n st[<\/span>i]<\/span> =<\/span> true<\/span>;<\/span>
    \n }<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <=<\/span> n;<\/span> i ++<\/span>)<\/span>
    \n if<\/span>(<\/span>!<\/span>st[<\/span>i]<\/span>)<\/span>
    \n dfs<\/span>(<\/span>i)<\/span>;<\/span><\/p>\n

    cout <<<\/span> ans <<<\/span> endl;<\/span><\/p>\n

    return<\/span> 0<\/span>;<\/span>
    \n}<\/span><\/p>\n

    Acwing 1074. \u4e8c\u53c9\u82f9\u679c\u6811<\/h3>\n

    \u6709\u4e00\u9897\u82f9\u679c\u6811，\u5982\u679c\u6811\u679d\u6709\u5206\u5c94，\u4e00\u5b9a\u662f\u5206\u4e24\u53c9，\u5373\u6ca1\u6709\u53ea\u6709\u4e00\u4e2a\u513f\u5b50\u7684\u8282\u70b9\u3002<\/p>\n

    \u8fd9\u68f5\u6811\u5171 <\/p>\n

    N <\/p>\n

    N <\/p>\n

    <\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>\u4e2a\u8282\u70b9，\u7f16\u53f7\u4e3a <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u81f3 <\/p>\n

    N <\/p>\n

    N <\/p>\n

    <\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>，\u6811\u6839\u7f16\u53f7\u4e00\u5b9a\u662f <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u6211\u4eec\u7528\u4e00\u6839\u6811\u679d\u4e24\u7aef\u8fde\u63a5\u7684\u8282\u70b9\u7f16\u53f7\u63cf\u8ff0\u4e00\u6839\u6811\u679d\u7684\u4f4d\u7f6e\u3002<\/p>\n

    \u4e00\u68f5\u82f9\u679c\u6811\u7684\u6811\u679d\u592a\u591a\u4e86，\u9700\u8981\u526a\u679d，\u4f46\u662f\u4e00\u4e9b\u6811\u679d\u4e0a\u957f\u6709\u82f9\u679c，\u7ed9\u5b9a\u9700\u8981\u4fdd\u7559\u7684\u6811\u679d\u6570\u91cf，\u6c42\u6700\u591a\u80fd\u7559\u4f4f\u591a\u5c11\u82f9\u679c，\u8fd9\u91cc\u7684\u4fdd\u7559\u662f\u6307\u6700\u7ec8\u4e0e <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u53f7\u70b9\u8fde\u901a\u3002<\/p>\n

    \u8f93\u5165\u683c\u5f0f<\/h4>\n

    \u7b2c\u4e00\u884c\u5305\u542b\u4e24\u4e2a\u6574\u6570 <\/p>\n

    N <\/p>\n

    N <\/p>\n

    <\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>\u548c <\/p>\n

    Q <\/p>\n

    Q <\/p>\n

    <\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>，\u5206\u522b\u8868\u793a\u6811\u7684\u8282\u70b9\u6570\u4ee5\u53ca\u8981\u4fdd\u7559\u7684\u6811\u679d\u6570\u91cf\u3002<\/p>\n

    \u63a5\u4e0b\u6765 <\/p>\n

    N <\/p>\n

    \u2212 <\/p>\n

    1 <\/p>\n

    N – 1 <\/p>\n

    <\/span><\/span>N<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u884c\u63cf\u8ff0\u6811\u679d\u4fe1\u606f，\u6bcf\u884c\u4e09\u4e2a\u6574\u6570，\u524d\u4e24\u4e2a\u662f\u5b83\u8fde\u63a5\u7684\u8282\u70b9\u7684\u7f16\u53f7，\u7b2c\u4e09\u4e2a\u6570\u662f\u8fd9\u6839\u6811\u679d\u4e0a\u82f9\u679c\u6570\u91cf\u3002<\/p>\n

    \u8f93\u51fa\u683c\u5f0f<\/h4>\n

    \u8f93\u51fa\u4ec5\u4e00\u884c，\u8868\u793a\u6700\u591a\u80fd\u7559\u4f4f\u7684\u6700\u591a\u7684\u82f9\u679c\u6570\u91cf\u3002<\/p>\n

    \u6570\u636e\u8303\u56f4<\/h4>\n

    <\/p>\n

    1 <\/p>\n

    < <\/p>\n

    Q <\/p>\n

    < <\/p>\n

    N <\/p>\n

    \u2264 <\/p>\n

    100 <\/p>\n

    1 < Q < N \\\\le 100 <\/p>\n

    <\/span><\/span>1<\/span><\/span><<\/span><\/span><\/span><\/span>Q<\/span><\/span><<\/span><\/span><\/span><\/span>N<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>100<\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u6bcf\u6839\u6811\u679d\u4e0a\u82f9\u679c\u4e0d\u8d85\u8fc7 <\/p>\n

    30000 <\/p>\n

    30000 <\/p>\n

    <\/span><\/span>30000<\/span><\/span><\/span><\/span><\/span>\u4e2a\u3002<\/p>\n

    \u601d\u8def<\/h4>\n

    \u5728[\u80cc\u5305\u6a21\u578b\u56db](\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0（Acwing\u63d0\u9ad8\u8bfe）—-\u52a8\u6001\u89c4\u5212\u00b7\u80cc\u5305\u6a21\u578b(\u56db）-CSDN\u535a\u5ba2)\u4e2d\u8bb2\u8fc7\u4e00\u9053\u6709\u4f9d\u8d56\u7684\u80cc\u5305\u95ee\u9898，\u5176\u5b9e\u8fd9\u9053\u9898\u548c\u90a3\u9053\u9898\u662f\u4e00\u6837\u7684，\u5c06\u82f9\u679c\u6570\u91cf\u653e\u5230\u6bcf\u4e2a\u70b9\u4e0a，\u8981\u9009\u62e9\u4e00\u4e2a\u70b9\u5c31\u8981\u9009\u62e9\u5b83\u7684\u7236\u8282\u70b9，\u5c06\u6240\u6709\u70b9\u7684\u4f53\u79ef\u770b\u4e3a <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>，\u603b\u7684\u4f53\u79ef\u5c31\u662f <\/p>\n

    Q <\/p>\n

    Q <\/p>\n

    <\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u4f46\u662f\u8fd9\u9898\u53ef\u4ee5\u8fdb\u4e00\u6b65\u7b80\u5316，\u4f7f\u7528 <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    j <\/p>\n

    ] <\/p>\n

    f[i][j] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>j<\/span>]<\/span><\/span><\/span><\/span><\/span>\u8868\u793a\u4ee5 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>\u4e3a\u6839\u7684\u5b50\u6811\u4e2d\u9009\u62e9 <\/p>\n

    j <\/p>\n

    j <\/p>\n

    <\/span><\/span>j<\/span><\/span><\/span><\/span><\/span>\u4e2a\u6811\u679d\u7684\u6700\u5927\u4ef7\u503c\u3002<\/p>\n

    \u5bf9\u4e8e\u72b6\u6001\u5212\u5206\u6765\u8bf4，\u5bf9\u4e8e\u6bcf\u4e2a\u5177\u6709\u4e24\u4e2a\u5206\u5c94\u7684\u5c0f\u5b50\u6811，\u5c06\u5176\u4e24\u4e2a\u5b50\u8282\u70b9\u770b\u6210\u662f\u4e00\u4e2a\u5206\u7ec4\u80cc\u5305\u95ee\u9898\u91cc\u7684\u4e24\u4e2a\u7269\u54c1\u7ec4，\u4e5f\u5c31\u662f\u5bf9\u4e8e\u4ee5 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>\u4e3a\u6839\u7684\u5b50\u6811\u6709\u4e24\u4e2a\u7269\u54c1 <\/p>\n

    s <\/p>\n

    1 <\/p>\n

    s_1 <\/p>\n

    <\/span><\/span>s<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u4e0e <\/p>\n

    s <\/p>\n

    2 <\/p>\n

    s_2 <\/p>\n

    <\/span><\/span>s<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5212\u5206\u4e3a\u5728 <\/p>\n

    s <\/p>\n

    1 <\/p>\n

    s_1 <\/p>\n

    <\/span><\/span>s<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u4e2d\u9009\u62e9 <\/p>\n

    0 <\/p>\n

    0 <\/p>\n

    <\/span><\/span>0<\/span><\/span><\/span><\/span><\/span>\u6761\u8fb9，\u90a3\u5c31\u662f <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    s <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    0 <\/p>\n

    ] <\/p>\n

    f[s_1][0] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>s<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>]<\/span>[<\/span>0<\/span>]<\/span><\/span><\/span><\/span><\/span>；\u9009\u62e9 <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u6761\u8fb9，\u90a3\u5c31\u662f <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    s <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    f[s_1][1] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>s<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>]<\/span>[<\/span>1<\/span>]<\/span><\/span><\/span><\/span><\/span>;\u4ee5\u6b64\u7c7b\u63a8，\u6700\u591a\u662f <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    s <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    j <\/p>\n

    \u2212 <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    f[s_1][j – 1] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>s<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>]<\/span>[<\/span>j<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span>]<\/span><\/span><\/span><\/span><\/span>，\u56e0\u4e3a\u8981\u9009\u62e9 <\/p>\n

    s <\/p>\n

    1 <\/p>\n

    s_1 <\/p>\n

    <\/span><\/span>s<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u5c31\u8981\u9009\u62e9 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>，\u4e5f\u5c31\u662f\u5fc5\u9009 <\/p>\n

    i <\/p>\n

    \u2192 <\/p>\n

    j <\/p>\n

    i \\\\rightarrow j <\/p>\n

    <\/span><\/span>i<\/span><\/span>\u2192<\/span><\/span><\/span><\/span>j<\/span><\/span><\/span><\/span><\/span>\u8fd9\u6761\u8fb9，\u5f53\u7136\u8ba1\u7b97\u7684\u65f6\u5019\u8981\u52a0\u4e0a\u8fd9\u6761\u8fb9\u7684\u6743\u91cd\u3002\u5bf9\u4e8e\u5b50\u6811 <\/p>\n

    s <\/p>\n

    2 <\/p>\n

    s_2 <\/p>\n

    <\/span><\/span>s<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u4e5f\u662f\u4e00\u6837\u7684\u3002<\/p>\n

    \u4ee3\u7801<\/h4>\n

    #<\/span>include<\/span> <iostream><\/span><\/span>
    \n#<\/span>include<\/span> <cstring><\/span><\/span>
    \n#<\/span>include<\/span> <cstdio><\/span><\/span>
    \n#<\/span>include<\/span> <algorithm><\/span><\/span><\/p>\n

    using<\/span> namespace<\/span> std;<\/span><\/p>\n

    const<\/span> int<\/span> N =<\/span> 110<\/span>,<\/span> M =<\/span> N *<\/span> 2<\/span>;<\/span><\/p>\n

    int<\/span> n,<\/span> m;<\/span>
    \nint<\/span> f[<\/span>N]<\/span>[<\/span>N]<\/span>;<\/span>
    \nint<\/span> h[<\/span>N]<\/span>,<\/span> e[<\/span>M]<\/span>,<\/span> ne[<\/span>M]<\/span>,<\/span> w[<\/span>M]<\/span>,<\/span> idx;<\/span><\/p>\n

    void<\/span> add<\/span>(<\/span>int<\/span> a,<\/span> int<\/span> b,<\/span> int<\/span> c)<\/span>
    \n{<\/span>
    \n w[<\/span>idx]<\/span> =<\/span> c,<\/span> e[<\/span>idx]<\/span> =<\/span> b,<\/span> ne[<\/span>idx]<\/span> =<\/span> h[<\/span>a]<\/span>,<\/span> h[<\/span>a]<\/span> =<\/span> idx ++<\/span>;<\/span>
    \n}<\/span><\/p>\n

    void<\/span> dfs<\/span>(<\/span>int<\/span> u,<\/span> int<\/span> father)<\/span>
    \n{<\/span>
    \n for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span> \/\/ \u679a\u4e3e\u7269\u54c1\u7ec4<\/span>
    \n {<\/span>
    \n if<\/span>(<\/span>e[<\/span>i]<\/span> ==<\/span> father)<\/span> continue<\/span>;<\/span>
    \n dfs<\/span>(<\/span>e[<\/span>i]<\/span>,<\/span> u)<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> j =<\/span> m;<\/span> j >=<\/span> 0<\/span>;<\/span> j —<\/span>)<\/span> \/\/ \u4f53\u79ef<\/span>
    \n for<\/span>(<\/span>int<\/span> k =<\/span> 0<\/span>;<\/span> k <<\/span> j;<\/span> k ++<\/span>)<\/span> \/\/ \u51b3\u7b56<\/span>
    \n f[<\/span>u]<\/span>[<\/span>j]<\/span> =<\/span> max<\/span>(<\/span>f[<\/span>u]<\/span>[<\/span>j]<\/span>,<\/span> f[<\/span>u]<\/span>[<\/span>j –<\/span> k –<\/span> 1<\/span>]<\/span> +<\/span> f[<\/span>e[<\/span>i]<\/span>]<\/span>[<\/span>k]<\/span> +<\/span> w[<\/span>i]<\/span>)<\/span>;<\/span>
    \n }<\/span>
    \n}<\/span><\/p>\n

    int<\/span> main<\/span>(<\/span>)<\/span>
    \n{<\/span>
    \n cin >><\/span> n >><\/span> m;<\/span><\/p>\n

    memset<\/span>(<\/span>h,<\/span> –<\/span>1<\/span>,<\/span> sizeof<\/span> h)<\/span>;<\/span>
    \n for<\/span>(<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n –<\/span> 1<\/span>;<\/span> i ++<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> a,<\/span> b,<\/span> c;<\/span>
    \n cin >><\/span> a >><\/span> b >><\/span> c;<\/span>
    \n add<\/span>(<\/span>a,<\/span> b,<\/span> c)<\/span>,<\/span> add<\/span>(<\/span>b,<\/span> a,<\/span> c)<\/span>;<\/span>
    \n }<\/span><\/p>\n

    dfs<\/span>(<\/span>1<\/span>,<\/span> –<\/span>1<\/span>)<\/span>;<\/span><\/p>\n

    cout <<<\/span> f[<\/span>1<\/span>]<\/span>[<\/span>m]<\/span> <<<\/span> endl;<\/span><\/p>\n

    return<\/span> 0<\/span>;<\/span>
    \n}<\/span><\/p>\n

    Acwing 323. \u6218\u7565\u6e38\u620f<\/h3>\n

    \u9c8d\u52c3\u559c\u6b22\u73a9\u7535\u8111\u6e38\u620f，\u7279\u522b\u662f\u6218\u7565\u6e38\u620f，\u4f46\u6709\u65f6\u4ed6\u627e\u4e0d\u5230\u89e3\u51b3\u95ee\u9898\u7684\u65b9\u6cd5，\u8fd9\u8ba9\u4ed6\u5f88\u4f24\u5fc3\u3002<\/p>\n

    \u73b0\u5728\u4ed6\u6709\u4ee5\u4e0b\u95ee\u9898\u3002<\/p>\n

    \u4ed6\u5fc5\u987b\u4fdd\u62a4\u4e00\u5ea7\u4e2d\u4e16\u7eaa\u57ce\u5e02，\u8fd9\u6761\u57ce\u5e02\u7684\u9053\u8def\u6784\u6210\u4e86\u4e00\u68f5\u6811\u3002<\/p>\n

    \u6bcf\u4e2a\u8282\u70b9\u4e0a\u7684\u58eb\u5175\u53ef\u4ee5\u89c2\u5bdf\u5230\u6240\u6709\u548c\u8fd9\u4e2a\u70b9\u76f8\u8fde\u7684\u8fb9\u3002<\/p>\n

    \u4ed6\u5fc5\u987b\u5728\u8282\u70b9\u4e0a\u653e\u7f6e\u6700\u5c11\u6570\u91cf\u7684\u58eb\u5175，\u4ee5\u4fbf\u4ed6\u4eec\u53ef\u4ee5\u89c2\u5bdf\u5230\u6240\u6709\u7684\u8fb9\u3002<\/p>\n

    \u4f60\u80fd\u5e2e\u52a9\u4ed6\u5417？<\/p>\n

    \u4f8b\u5982，\u4e0b\u9762\u7684\u6811：<\/p>\n

    \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

    \u53ea\u9700\u8981\u653e\u7f6e <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u540d\u58eb\u5175（\u5728\u8282\u70b9 <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u5904），\u5c31\u53ef\u89c2\u5bdf\u5230\u6240\u6709\u7684\u8fb9\u3002<\/p>\n

    \u8f93\u5165\u683c\u5f0f<\/h4>\n

    \u8f93\u5165\u5305\u542b\u591a\u7ec4\u6d4b\u8bd5\u6570\u636e，\u6bcf\u7ec4\u6d4b\u8bd5\u6570\u636e\u7528\u4ee5\u63cf\u8ff0\u4e00\u68f5\u6811\u3002<\/p>\n

    \u5bf9\u4e8e\u6bcf\u7ec4\u6d4b\u8bd5\u6570\u636e，\u7b2c\u4e00\u884c\u5305\u542b\u6574\u6570 <\/p>\n

    N <\/p>\n

    N <\/p>\n

    <\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>，\u8868\u793a\u6811\u7684\u8282\u70b9\u6570\u76ee\u3002<\/p>\n

    \u63a5\u4e0b\u6765 <\/p>\n

    N <\/p>\n

    N <\/p>\n

    <\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u884c，\u6bcf\u884c\u6309\u5982\u4e0b\u65b9\u6cd5\u63cf\u8ff0\u4e00\u4e2a\u8282\u70b9\u3002<\/p>\n

    \u8282\u70b9\u7f16\u53f7：(\u5b50\u8282\u70b9\u6570\u76ee) \u5b50\u8282\u70b9 \u5b50\u8282\u70b9 \u2026<\/p>\n

    \u8282\u70b9\u7f16\u53f7\u4ece <\/p>\n

    0 <\/p>\n

    0 <\/p>\n

    <\/span><\/span>0<\/span><\/span><\/span><\/span><\/span> \u5230 <\/p>\n

    N <\/p>\n

    \u2212 <\/p>\n

    1 <\/p>\n

    N\u22121 <\/p>\n

    <\/span><\/span>N<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>，\u6bcf\u4e2a\u8282\u70b9\u7684\u5b50\u8282\u70b9\u6570\u91cf\u5747\u4e0d\u8d85\u8fc7 <\/p>\n

    10 <\/p>\n

    10 <\/p>\n

    <\/span><\/span>10<\/span><\/span><\/span><\/span><\/span>，\u6bcf\u4e2a\u8fb9\u5728\u8f93\u5165\u6570\u636e\u4e2d\u53ea\u51fa\u73b0\u4e00\u6b21\u3002<\/p>\n

    \u8f93\u51fa\u683c\u5f0f<\/h4>\n

    \u5bf9\u4e8e\u6bcf\u7ec4\u6d4b\u8bd5\u6570\u636e，\u8f93\u51fa\u4e00\u4e2a\u5360\u636e\u4e00\u884c\u7684\u7ed3\u679c，\u8868\u793a\u6700\u5c11\u9700\u8981\u7684\u58eb\u5175\u6570\u3002<\/p>\n

    \u6570\u636e\u8303\u56f4<\/h4>\n

    <\/p>\n

    0 <\/p>\n

    < <\/p>\n

    N <\/p>\n

    \u2264 <\/p>\n

    1500 <\/p>\n

    0 < N \\\\le 1500 <\/p>\n

    <\/span><\/span>0<\/span><\/span><<\/span><\/span><\/span><\/span>N<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>1500<\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u601d\u8def<\/h4>\n

    \u8fd9\u9053\u9898\u7684\u9898\u610f\u662f\u5bf9\u4e8e\u4e00\u9897\u6811，\u9009\u62e9\u6700\u5c11\u7684\u8282\u70b9\u6570\u8986\u76d6\u6240\u6709\u7684\u8fb9，\u8fd9\u4e2a\u5176\u5b9e\u548c\u6ca1\u6709\u4e0a\u53f8\u7684\u821e\u4f1a\u5f88\u50cf，\u5728\u6ca1\u6709\u4e0a\u53f8\u7684\u821e\u4f1a\u4e2d，\u6211\u4eec\u6c42\u7684\u662f\u6bcf\u6761\u8fb9\u4e0a\u6700\u591a\u4ec5\u9009\u62e9\u4e00\u4e2a\u70b9\u6c42\u6700\u5927\u503c，\u5c5e\u4e8e\u6700\u5927\u72ec\u7acb\u96c6\u95ee\u9898，\u800c\u8fd9\u9053\u9898\u4e2d，\u6bcf\u6761\u8fb9\u4e0a\u81f3\u5c11\u9009\u62e9\u4e00\u4e2a\u70b9\u6c42\u6700\u5c0f\u503c，\u8fd9\u4e24\u4e2a\u662f\u5bf9\u79f0\u7684\u95ee\u9898\u3002<\/p>\n

    \u72b6\u6001\u8ba1\u7b97\u548c\u72b6\u6001\u8f6c\u79fb\u4e5f\u5f88\u7b80\u5355，\u76f4\u63a5\u770b\u4ee3\u7801\u53ed\u3002<\/p>\n

    \u4ee3\u7801<\/h4>\n

    #<\/span>include<\/span> <iostream><\/span><\/span>
    \n#<\/span>include<\/span> <cstring><\/span><\/span>
    \n#<\/span>include<\/span> <cstdio><\/span><\/span>
    \n#<\/span>include<\/span> <algorithm><\/span><\/span><\/p>\n

    using<\/span> namespace<\/span> std;<\/span><\/p>\n

    const<\/span> int<\/span> N =<\/span> 1600<\/span>;<\/span><\/p>\n

    int<\/span> n;<\/span>
    \nint<\/span> f[<\/span>N]<\/span>[<\/span>2<\/span>]<\/span>;<\/span>
    \nint<\/span> h[<\/span>N]<\/span>,<\/span> e[<\/span>N]<\/span>,<\/span> ne[<\/span>N]<\/span>,<\/span> idx;<\/span>
    \nbool<\/span> st[<\/span>N]<\/span>;<\/span><\/p>\n

    void<\/span> add<\/span>(<\/span>int<\/span> a,<\/span> int<\/span> b)<\/span>
    \n{<\/span>
    \n e[<\/span>idx]<\/span> =<\/span> b,<\/span> ne[<\/span>idx]<\/span> =<\/span> h[<\/span>a]<\/span>,<\/span> h[<\/span>a]<\/span> =<\/span> idx ++<\/span>;<\/span>
    \n}<\/span><\/p>\n

    void<\/span> dfs<\/span>(<\/span>int<\/span> u)<\/span>
    \n{<\/span>
    \n f[<\/span>u]<\/span>[<\/span>0<\/span>]<\/span> =<\/span> 0<\/span>;<\/span>
    \n f[<\/span>u]<\/span>[<\/span>1<\/span>]<\/span> =<\/span> 1<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span><\/p>\n

    dfs<\/span>(<\/span>j)<\/span>;<\/span><\/p>\n

    f[<\/span>u]<\/span>[<\/span>0<\/span>]<\/span> +=<\/span> f[<\/span>j]<\/span>[<\/span>1<\/span>]<\/span>;<\/span>
    \n f[<\/span>u]<\/span>[<\/span>1<\/span>]<\/span> +=<\/span> min<\/span>(<\/span>f[<\/span>j]<\/span>[<\/span>0<\/span>]<\/span>,<\/span> f[<\/span>j]<\/span>[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>
    \n }<\/span>
    \n}<\/span><\/p>\n

    int<\/span> main<\/span>(<\/span>)<\/span>
    \n{<\/span>
    \n while<\/span>(<\/span>scanf<\/span>(<\/span>"%d"<\/span>,<\/span> &<\/span>n)<\/span> !=<\/span> –<\/span>1<\/span>)<\/span>
    \n {<\/span>
    \n idx =<\/span> 0<\/span>;<\/span>
    \n memset<\/span>(<\/span>h,<\/span> –<\/span>1<\/span>,<\/span> sizeof<\/span> h)<\/span>;<\/span>
    \n memset<\/span>(<\/span>st,<\/span> 0<\/span>,<\/span> sizeof<\/span> st)<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i ++<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> cnt;<\/span>
    \n int<\/span> id;<\/span>
    \n scanf<\/span>(<\/span>"%d:(%d)"<\/span>,<\/span> &<\/span>id,<\/span> &<\/span>cnt)<\/span>;<\/span><\/p>\n

    while<\/span>(<\/span>cnt —<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> ver;<\/span>
    \n cin >><\/span> ver;<\/span>
    \n add<\/span>(<\/span>id,<\/span> ver)<\/span>;<\/span>
    \n st[<\/span>ver]<\/span> =<\/span> true<\/span>;<\/span>
    \n }<\/span><\/p>\n

    }<\/span>
    \n int<\/span> root =<\/span> 0<\/span>;<\/span>
    \n while<\/span>(<\/span>st[<\/span>root]<\/span>)<\/span> root ++<\/span>;<\/span><\/p>\n

    dfs<\/span>(<\/span>root)<\/span>;<\/span>
    \n cout <<<\/span> min<\/span>(<\/span>f[<\/span>root]<\/span>[<\/span>1<\/span>]<\/span>,<\/span> f[<\/span>root]<\/span>[<\/span>0<\/span>]<\/span>)<\/span> <<<\/span> endl;<\/span>
    \n }<\/span><\/p>\n

    return<\/span> 0<\/span>;<\/span>
    \n}<\/span><\/p>\n

    Acwing 1077. \u7687\u5bab\u770b\u5b88<\/h3>\n

    \u592a\u5e73\u738b\u4e16\u5b50\u4e8b\u4ef6\u540e，\u9646\u5c0f\u51e4\u6210\u4e86\u7687\u4e0a\u7279\u8058\u7684\u5fa1\u524d\u4e00\u54c1\u4f8d\u536b\u3002<\/p>\n

    \u7687\u5bab\u4ee5\u5348\u95e8\u4e3a\u8d77\u70b9，\u76f4\u5230\u540e\u5bab\u5ad4\u5983\u4eec\u7684\u5bdd\u5bab，\u5448\u4e00\u68f5\u6811\u7684\u5f62\u72b6，\u67d0\u4e9b\u5bab\u6bbf\u95f4\u53ef\u4ee5\u4e92\u76f8\u671b\u89c1\u3002<\/p>\n

    \u5927\u5185\u4fdd\u536b\u68ee\u4e25，\u4e09\u6b65\u4e00\u5c97，\u4e94\u6b65\u4e00\u54e8，\u6bcf\u4e2a\u5bab\u6bbf\u90fd\u8981\u6709\u4eba\u5168\u5929\u5019\u770b\u5b88，\u5728\u4e0d\u540c\u7684\u5bab\u6bbf\u5b89\u6392\u770b\u5b88\u6240\u9700\u7684\u8d39\u7528\u4e0d\u540c\u3002<\/p>\n

    \u53ef\u662f\u9646\u5c0f\u51e4\u624b\u4e0a\u7684\u7ecf\u8d39\u4e0d\u8db3，\u65e0\u8bba\u5982\u4f55\u4e5f\u6ca1\u6cd5\u5728\u6bcf\u4e2a\u5bab\u6bbf\u90fd\u5b89\u7f6e\u7559\u5b88\u4f8d\u536b\u3002<\/p>\n

    \u5e2e\u52a9\u9646\u5c0f\u51e4\u5e03\u7f6e\u4f8d\u536b，\u5728\u770b\u5b88\u5168\u90e8\u5bab\u6bbf\u7684\u524d\u63d0\u4e0b，\u4f7f\u5f97\u82b1\u8d39\u7684\u7ecf\u8d39\u6700\u5c11\u3002<\/p>\n

    \u8f93\u5165\u683c\u5f0f<\/h4>\n

    \u8f93\u5165\u4e2d\u6570\u636e\u63cf\u8ff0\u4e00\u68f5\u6811，\u63cf\u8ff0\u5982\u4e0b：<\/p>\n

    \u7b2c\u4e00\u884c <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>，\u8868\u793a\u6811\u4e2d\u7ed3\u70b9\u7684\u6570\u76ee\u3002<\/p>\n

    \u7b2c\u4e8c\u884c\u81f3\u7b2c <\/p>\n

    n <\/p>\n

    + <\/p>\n

    1 <\/p>\n

    n + 1 <\/p>\n

    <\/span><\/span>n<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u884c，\u6bcf\u884c\u63cf\u8ff0\u6bcf\u4e2a\u5bab\u6bbf\u7ed3\u70b9\u4fe1\u606f，\u4f9d\u6b21\u4e3a：\u8be5\u5bab\u6bbf\u7ed3\u70b9\u6807\u53f7\u4e3a <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>，\u5728\u8be5\u5bab\u6bbf\u5185\u5b89\u7f6e\u4f8d\u536b\u6240\u9700\u7684\u7ecf\u8d39 <\/p>\n

    k <\/p>\n

    k <\/p>\n

    <\/span><\/span>k<\/span><\/span><\/span><\/span><\/span>，\u8be5\u8fb9\u7684\u513f\u5b50\u6570 <\/p>\n

    m <\/p>\n

    m <\/p>\n

    <\/span><\/span>m<\/span><\/span><\/span><\/span><\/span>，\u63a5\u4e0b\u6765 <\/p>\n

    m <\/p>\n

    m <\/p>\n

    <\/span><\/span>m<\/span><\/span><\/span><\/span><\/span>\u4e2a\u6570，\u5206\u522b\u662f\u8fd9\u4e2a\u7ed3\u70b9\u7684 <\/p>\n

    m <\/p>\n

    m <\/p>\n

    <\/span><\/span>m<\/span><\/span><\/span><\/span><\/span>\u4e2a\u513f\u5b50\u7684\u7f16\u53f7 <\/p>\n

    r <\/p>\n

    1 <\/p>\n

    , <\/p>\n

    r <\/p>\n

    2 <\/p>\n

    , <\/p>\n

    \u22ef
    \n \u2009 <\/p>\n

    , <\/p>\n

    r <\/p>\n

    m <\/p>\n

    r_1, r_2, \\\\cdots, r_m <\/p>\n

    <\/span><\/span>r<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>r<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>r<\/span><\/span>m<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5bf9\u4e8e\u4e00\u4e2a <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u4e2a\u8282\u70b9\u7684\u6811，\u7ed3\u70b9\u6807\u53f7\u5728 <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u5230 <\/p>\n

    n <\/p>\n

    n <\/p>\n

    <\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4，\u4e14\u6807\u53f7\u4e0d\u91cd\u590d\u3002<\/p>\n

    \u8f93\u51fa\u683c\u5f0f<\/h4>\n

    \u8f93\u51fa\u6700\u5c11\u7684\u7ecf\u8d39\u3002<\/p>\n

    \u6570\u636e\u8303\u56f4<\/h4>\n

    <\/p>\n

    0 <\/p>\n

    < <\/p>\n

    N <\/p>\n

    \u2264 <\/p>\n

    1500 <\/p>\n

    0 < N \\\\le 1500 <\/p>\n

    <\/span><\/span>0<\/span><\/span><<\/span><\/span><\/span><\/span>N<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>1500<\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u601d\u8def<\/h4>\n

    \u5728\u8fd9\u9898\u4e2d，\u540c\u6837\u662f\u6311\u9009\u8db3\u591f\u7684\u70b9\u5b8c\u6210\u6574\u9897\u6811\u7684\u8986\u76d6，\u4f46\u662f\u5bf9\u4e8e\u6bcf\u6761\u8fb9\u6765\u8bf4，\u8fd9\u4e00\u9898\u7684\u72b6\u6001\u8868\u793a\u4e0e\u4e4b\u524d\u5e76\u4e0d\u4e00\u6837，\u4f7f\u7528 <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    0 <\/p>\n

    ] <\/p>\n

    f[i][0] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>0<\/span>]<\/span><\/span><\/span><\/span><\/span>\u8868\u793a\u70b9 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>\u88ab\u7236\u8282\u70b9\u770b\u5230\u7684\u6700\u5c0f\u82b1\u8d39， <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    f[i][1] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>1<\/span>]<\/span><\/span><\/span><\/span><\/span>\u8868\u793a\u70b9 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>\u88ab\u5b50\u8282\u70b9\u770b\u5230\u7684\u6700\u5c0f\u82b1\u8d39， <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    2 <\/p>\n

    ] <\/p>\n

    f[i][2] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>2<\/span>]<\/span><\/span><\/span><\/span><\/span>\u8868\u793a\u70b9 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>\u4e0a\u6446\u653e\u5b88\u536b\u7684\u6700\u5c0f\u82b1\u8d39\u3002<\/p>\n

    \u5bf9\u4e8e\u72b6\u6001\u8f6c\u79fb，\u5f53\u8282\u70b9\u72b6\u6001\u4e3a <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    0 <\/p>\n

    ] <\/p>\n

    f[i][0] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>0<\/span>]<\/span><\/span><\/span><\/span><\/span>\u65f6，\u90a3\u4e48\u4ed6\u7684\u6700\u5c0f\u82b1\u8d39\u5c31\u662f\u4ed6\u7684\u6240\u6709\u5b50\u8282\u70b9\u72b6\u6001\u4e3a <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u6216 <\/p>\n

    2 <\/p>\n

    2 <\/p>\n

    <\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u65f6\u7684\u548c，\u4f46\u662f\u4ed6\u7684\u5b50\u8282\u70b9\u4e0d\u53ef\u80fd\u662f <\/p>\n

    0 <\/p>\n

    0 <\/p>\n

    <\/span><\/span>0<\/span><\/span><\/span><\/span><\/span>，\u56e0\u4e3a <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>\u662f <\/p>\n

    0 <\/p>\n

    0 <\/p>\n

    <\/span><\/span>0<\/span><\/span><\/span><\/span><\/span>，\u8868\u793a\u6ca1\u6709\u653e\u4f8d\u536b，\u5c31\u4e0d\u53ef\u80fd\u770b\u5230\u4ed6\u7684\u5b50\u8282\u70b9，\u6240\u4ee5\u4ed6\u7684\u5b50\u8282\u70b9\u53ea\u80fd\u662f\u53e6\u5916\u4e24\u79cd\u72b6\u6001；\u5f53\u8282\u70b9\u72b6\u6001\u4e3a <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    2 <\/p>\n

    ] <\/p>\n

    f[i][2] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>2<\/span>]<\/span><\/span><\/span><\/span><\/span>\u65f6，\u5b83\u7684\u5b50\u8282\u70b9\u53ef\u4ee5\u662f\u4e09\u79cd\u72b6\u6001，\u56e0\u4e3a\u5b83\u4e0a\u9762\u653e\u4e86\u4f8d\u536b；\u5f53\u8282\u70b9\u72b6\u6001\u4e3a <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    i <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    1 <\/p>\n

    ] <\/p>\n

    f[i][1] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>i<\/span>]<\/span>[<\/span>1<\/span>]<\/span><\/span><\/span><\/span><\/span>\u65f6，\u8868\u793a\u4ed6\u662f\u88ab\u5b50\u8282\u70b9\u770b\u5230\u7684，\u56e0\u6b64\u9700\u8981\u679a\u4e3e\u662f\u54ea\u4e2a\u5b50\u8282\u70b9\u770b\u5230\u7684\u5b83，\u7136\u540e\u53d6\u6700\u5c0f\u503c\u5c31\u884c，\u5047\u8bbe\u662f <\/p>\n

    k <\/p>\n

    k <\/p>\n

    <\/span><\/span>k<\/span><\/span><\/span><\/span><\/span>\u8fd9\u4e2a\u7ed3\u70b9\u770b\u5230\u4e86 <\/p>\n

    i <\/p>\n

    i <\/p>\n

    <\/span><\/span>i<\/span><\/span><\/span><\/span><\/span>，\u90a3\u4e48\u4e00\u5b9a\u8981\u6709 <\/p>\n

    f <\/p>\n

    [ <\/p>\n

    k <\/p>\n

    ] <\/p>\n

    [ <\/p>\n

    2 <\/p>\n

    ] <\/p>\n

    f[k][2] <\/p>\n

    <\/span><\/span>f<\/span>[<\/span>k<\/span>]<\/span>[<\/span>2<\/span>]<\/span><\/span><\/span><\/span><\/span>，\u5176\u4ed6\u7684\u5b50\u8282\u70b9\u53ef\u4ee5\u662f <\/p>\n

    1 <\/p>\n

    1 <\/p>\n

    <\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u548c <\/p>\n

    2 <\/p>\n

    2 <\/p>\n

    <\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u4ee3\u7801<\/h4>\n

    #<\/span>include<\/span> <iostream><\/span><\/span>
    \n#<\/span>include<\/span> <cstdio><\/span><\/span>
    \n#<\/span>include<\/span> <cstring><\/span><\/span>
    \n#<\/span>include<\/span> <algorithm><\/span><\/span><\/p>\n

    using<\/span> namespace<\/span> std;<\/span><\/p>\n

    const<\/span> int<\/span> N =<\/span> 1510<\/span>;<\/span><\/p>\n

    int<\/span> n;<\/span>
    \nint<\/span> f[<\/span>N]<\/span>[<\/span>3<\/span>]<\/span>;<\/span>
    \nint<\/span> h[<\/span>N]<\/span>,<\/span> e[<\/span>N]<\/span>,<\/span> w[<\/span>N]<\/span>,<\/span> ne[<\/span>N]<\/span>,<\/span> idx;<\/span>
    \nbool<\/span> st[<\/span>N]<\/span>;<\/span><\/p>\n

    void<\/span> add<\/span>(<\/span>int<\/span> a,<\/span> int<\/span> b)<\/span>
    \n{<\/span>
    \n e[<\/span>idx]<\/span> =<\/span> b,<\/span> ne[<\/span>idx]<\/span> =<\/span> h[<\/span>a]<\/span>,<\/span> h[<\/span>a]<\/span> =<\/span> idx ++<\/span>;<\/span>
    \n}<\/span><\/p>\n

    void<\/span> dfs<\/span>(<\/span>int<\/span> u)<\/span>
    \n{<\/span>
    \n f[<\/span>u]<\/span>[<\/span>2<\/span>]<\/span> =<\/span> w[<\/span>u]<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span><\/p>\n

    dfs<\/span>(<\/span>j)<\/span>;<\/span><\/p>\n

    f[<\/span>u]<\/span>[<\/span>0<\/span>]<\/span> +=<\/span> min<\/span>(<\/span>f[<\/span>j]<\/span>[<\/span>1<\/span>]<\/span>,<\/span> f[<\/span>j]<\/span>[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
    \n f[<\/span>u]<\/span>[<\/span>2<\/span>]<\/span> +=<\/span> min<\/span>(<\/span>f[<\/span>j]<\/span>[<\/span>0<\/span>]<\/span>,<\/span> min<\/span>(<\/span>f[<\/span>j]<\/span>[<\/span>1<\/span>]<\/span>,<\/span> f[<\/span>j]<\/span>[<\/span>2<\/span>]<\/span>)<\/span>)<\/span>;<\/span>
    \n }<\/span><\/p>\n

    f[<\/span>u]<\/span>[<\/span>1<\/span>]<\/span> =<\/span> 1e9<\/span>;<\/span><\/p>\n

    for<\/span>(<\/span>int<\/span> i =<\/span> h[<\/span>u]<\/span>;<\/span> i !=<\/span> –<\/span>1<\/span>;<\/span> i =<\/span> ne[<\/span>i]<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> j =<\/span> e[<\/span>i]<\/span>;<\/span> \/\/ \u679a\u4e3e\u662f\u54ea\u4e2a\u5b50\u8282\u70b9\u770b\u5230\u5f53\u524d\u8282\u70b9u<\/span><\/p>\n

    f[<\/span>u]<\/span>[<\/span>1<\/span>]<\/span> =<\/span> min<\/span>(<\/span>f[<\/span>u]<\/span>[<\/span>1<\/span>]<\/span>,<\/span> f[<\/span>j]<\/span>[<\/span>2<\/span>]<\/span> +<\/span> f[<\/span>u]<\/span>[<\/span>0<\/span>]<\/span> –<\/span> min<\/span>(<\/span>f[<\/span>j]<\/span>[<\/span>1<\/span>]<\/span>,<\/span> f[<\/span>j]<\/span>[<\/span>2<\/span>]<\/span>)<\/span>)<\/span>;<\/span>
    \n }<\/span>
    \n}<\/span><\/p>\n

    int<\/span> main<\/span>(<\/span>)<\/span>
    \n{<\/span>
    \n cin >><\/span> n;<\/span><\/p>\n

    memset<\/span>(<\/span>h,<\/span> –<\/span>1<\/span>,<\/span> sizeof<\/span> h)<\/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> id,<\/span> cnt,<\/span> cost;<\/span>
    \n cin >><\/span> id >><\/span> cost >><\/span> cnt;<\/span>
    \n w[<\/span>id]<\/span> =<\/span> cost;<\/span>
    \n while<\/span>(<\/span>cnt —<\/span>)<\/span>
    \n {<\/span>
    \n int<\/span> ver;<\/span>
    \n cin >><\/span> ver;<\/span>
    \n add<\/span>(<\/span>id,<\/span> ver)<\/span>;<\/span>
    \n st[<\/span>ver]<\/span> =<\/span> true<\/span>;<\/span>
    \n }<\/span>
    \n }<\/span><\/p>\n

    int<\/span> root =<\/span> 1<\/span>;<\/span>
    \n while<\/span>(<\/span>st[<\/span>root]<\/span>)<\/span> root ++<\/span>;<\/span><\/p>\n

    dfs<\/span>(<\/span>root)<\/span>;<\/span><\/p>\n

    cout <<<\/span> min<\/span>(<\/span>f[<\/span>root]<\/span>[<\/span>1<\/span>]<\/span>,<\/span> f[<\/span>root]<\/span>[<\/span>2<\/span>]<\/span>)<\/span> <<<\/span> endl;<\/span><\/p>\n

    return<\/span> 0<\/span>;<\/span>
    \n}<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

    \u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb678\u6b21\uff0c\u70b9\u8d5e11\u6b21\uff0c\u6536\u85cf21\u6b21\u3002@ author: \u660e\u6708\u6e05\u4e86\u4e2a\u98ceps\u2b50\ufe0f\u6811\u5f62\u52a8\u6001\u89c4\u5212\uff08\u6811\u5f62DP\uff09\u662f\u5904\u7406\u6811\u7ed3\u6784\u95ee\u9898\u7684\u4e00\u79cd\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\uff0c\u7279\u5f81\u4e5f\u5f88\u660e\u663e\uff0c\u4f1a\u6709\u4e00\u4e2a\u6811\u5f62\u7ed3\u6784\uff0c\u5176\u5b9e\u662fDFS\u7684\u4f18\u5316\u3002<\/p>\n","protected":false},"author":2,"featured_media":42182,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[2865,371,3906,3907,305],"topic":[],"class_list":["post-42184","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-2865","tag-371","tag-3906","tag-dp","tag-305"],"yoast_head":"\n\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/42184.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb678\u6b21\uff0c\u70b9\u8d5e11\u6b21\uff0c\u6536\u85cf21\u6b21\u3002@ author: \u660e\u6708\u6e05\u4e86\u4e2a\u98ceps\u2b50\ufe0f\u6811\u5f62\u52a8\u6001\u89c4\u5212\uff08\u6811\u5f62DP\uff09\u662f\u5904\u7406\u6811\u7ed3\u6784\u95ee\u9898\u7684\u4e00\u79cd\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\uff0c\u7279\u5f81\u4e5f\u5f88\u660e\u663e\uff0c\u4f1a\u6709\u4e00\u4e2a\u6811\u5f62\u7ed3\u6784\uff0c\u5176\u5b9e\u662fDFS\u7684\u4f18\u5316\u3002\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/42184.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2025-06-06T10:25:53+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/06\/20250606102550-6842c22e742bc.jpg\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"11 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/42184.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/42184.html\",\"name\":\"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2025-06-06T10:25:53+00:00\",\"dateModified\":\"2025-06-06T10:25:53+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/42184.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/42184.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/42184.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09----\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/42184.html","og_locale":"zh_CN","og_type":"article","og_title":"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb678\u6b21\uff0c\u70b9\u8d5e11\u6b21\uff0c\u6536\u85cf21\u6b21\u3002@ author: \u660e\u6708\u6e05\u4e86\u4e2a\u98ceps\u2b50\ufe0f\u6811\u5f62\u52a8\u6001\u89c4\u5212\uff08\u6811\u5f62DP\uff09\u662f\u5904\u7406\u6811\u7ed3\u6784\u95ee\u9898\u7684\u4e00\u79cd\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\uff0c\u7279\u5f81\u4e5f\u5f88\u660e\u663e\uff0c\u4f1a\u6709\u4e00\u4e2a\u6811\u5f62\u7ed3\u6784\uff0c\u5176\u5b9e\u662fDFS\u7684\u4f18\u5316\u3002","og_url":"https:\/\/www.wsisp.com\/helps\/42184.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2025-06-06T10:25:53+00:00","og_image":[{"url":"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/06\/20250606102550-6842c22e742bc.jpg"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"11 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/42184.html","url":"https:\/\/www.wsisp.com\/helps\/42184.html","name":"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09-\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2025-06-06T10:25:53+00:00","dateModified":"2025-06-06T10:25:53+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/42184.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/42184.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/42184.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0\uff08Acwing \u63d0\u9ad8\u8bfe\uff09----\u52a8\u6001\u89c4\u5212\u00b7\u6811\u5f62DP"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/42184","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=42184"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/42184\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media\/42182"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=42184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=42184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=42184"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=42184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}