{"id":29,"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-16-%e6%a0%91%e5%bd%a2dp%e7%ad%89%e5%b7%ae%e6%95%b0%e5%88%97%e5%89%8d%e7%bc%80%e5%92%8c\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-16-%e6%a0%91%e5%bd%a2dp%e7%ad%89%e5%b7%ae%e6%95%b0%e5%88%97%e5%89%8d%e7%bc%80%e5%92%8c","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-16-%e6%a0%91%e5%bd%a2dp%e7%ad%89%e5%b7%ae%e6%95%b0%e5%88%97%e5%89%8d%e7%bc%80%e5%92%8c\/","title":{"rendered":"2020-08-16 \u6811\u5f62DP+\u7b49\u5dee\u6570\u5217\u524d\u7f00\u548c"},"content":{"rendered":"

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

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

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

eobiyye\u7ed9\u4e86\u4f60\u4e00\u4e2a\u957f\u5ea6\u4e3an\u7684\u5e8f\u5217ai\uff0c\u5e8f\u5217\u4e2d\u6bcf\u4e2a\u5143\u7d20\u7684\u521d\u59cb\u503c\u4e3a0\u3002
\u63a5\u4e0b\u6765\u5979\u4f1a\u5bf9\u8fd9\u4e2a\u5e8f\u5217\u8fdb\u884cm\u6b21\u64cd\u4f5c\uff0c\u6bcf\u6b21\u64cd\u4f5c\u67094\u4e2a\u53c2\u6570l,r,s,e\uff0c\u8868\u793a\u5c06\u533a\u95f4[l,r]\u52a0\u4e0a\u4e00\u4e2a\u9996\u9879\u4e3as\uff0c\u672b\u9879\u4e3ae\u7684\u7b49\u5dee\u6570\u5217\u3002
\u82e5\u4e00\u6b21\u64cd\u4f5c\u4e2dl=1,r=5,s=2,e=10\uff0c\u5219\u5bf9\u5e8f\u5217\u4e2d\u7b2c1~5\u4e2a\u6570\u5206\u522b\u52a0\u4e0a2,4,6,8,10\u3002
\u73b0\u5728Geobiyye\u8981\u6c42\u4f60\u6c42\u51fam\u6b21\u64cd\u4f5c\u540e\u5e8f\u5217\u4e2d\u7684\u6bcf\u4e2a\u6570\u7684\u503c\u3002<\/p>\n

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

\u7b2c\u4e00\u884c2\u4e2a\u6574\u6570n,m\uff0c\u8868\u793a\u5e8f\u5217\u957f\u5ea6\u548c\u64cd\u4f5c\u6570\u3002
\u63a5\u4e0b\u6765m\u884c\uff0c\u6bcf\u884c4\u4e2a\u6574\u6570l,r,s,e\uff0c\u542b\u4e49\u89c1\u9898\u76ee\u63cf\u8ff0\u3002
\u6570\u636e\u4fdd\u8bc1\u7b49\u5dee\u6570\u5217\u4e2d\u7684\u6bcf\u4e00\u9879\u90fd\u662f\u6574\u6570\u3002<\/p>\n

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

\u7531\u4e8e\u8f93\u51fa\u6570\u636e\u8fc7\u5927\uff0cGeobiyye\u53ea\u60f3\u8981\u77e5\u9053\u6700\u7ec8\u5e8f\u5217\u6bcf\u4e00\u9879\u7684\u5f02\u6216\u548c\uff0c\u5373\u3002\uff08\u5176\u4e2d\u8868\u793a\u4e8c\u8fdb\u5236\u4e0b\u7684\u5f02\u6216\u64cd\u4f5c\uff0c\u5728c++\u4e2d\u4e3a^\uff09<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
5 2\n1 5 2 10\n2 4 1 1\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
3\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u89e3\u91ca\uff1a<\/h5>\n
\u7b2c\u4e00\u6b21\u64cd\u4f5c\u52a0\u7684\u6570\u5217\uff1a2 4 6 8 10
 \u7b2c\u4e8c\u6b21\u64cd\u4f5c\u52a0\u7684\u6570\u5217\uff1a0 1 1 1 0
 \u6240\u6709\u64cd\u4f5c\u7ed3\u675f\u540e\u5e8f\u5217\u6bcf\u4e2a\u5143\u7d20\u503c\u4e3a\uff1a2 5 7 9 10\u3002
 \u8f93\u51fa\u5f02\u6216\u548c\uff0c\u5c31\u662f3\u3002<\/p>\n
\u3010\u6570\u636e\u8303\u56f4\u3011
 \u5bf9\u4e8e30%\u7684\u6570\u636e\uff1an,m\u22641000 \u3002
 \u5bf9\u4e8e50%\u7684\u6570\u636e\uff1an,m\u2264100000\u3002
 \u5bf9\u4e8e\u53e6\u591620%\u7684\u6570\u636e\uff1as=e\u3002
 \u5bf9\u4e8e100%\u7684\u6570\u636e\uff1an,m\u2264500000,1\u2264l\uff1cr\u2264n\u3002
 \u6570\u636e\u4fdd\u8bc1\u8f93\u5165\u6570\u636e\u4ee5\u53ca\u5728\u4efb\u4f55\u65f6\u5019\u5e8f\u5217\u4e2d\u7684\u6570\u5728[0,9\u00d71018]\u8303\u56f4\u5185\u3002<\/p>\n
\u7b49\u5dee\u6570\u5217\u7684\u524d\u7f00\u548c<\/p>\n
#include<\/span><\/span><\/span>\n \nusing<\/span> namespace<\/span> std;<\/span>\nconst<\/span> long<\/span> long<\/span> int<\/span> N=<\/span>1e7<\/span>+<\/span>500<\/span>;<\/span>\nlong<\/span> long<\/span> int<\/span> out[<\/span>N]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    std::<\/span>ios::<\/span>sync_with_stdio<\/span>(<\/span>false<\/span>)<\/span>;<\/span>\n    std::<\/span>cin.<\/span>tie<\/span>(<\/span>0<\/span>)<\/span>;<\/span>\n    register<\/span> long<\/span> long<\/span> int<\/span> n,<\/span>m,<\/span>l,<\/span>r,<\/span>ks,<\/span>e1,<\/span>dc,<\/span>tmp=<\/span>0<\/span>;<\/span>\n    register<\/span> long<\/span> long<\/span> int<\/span> max1=<\/span>0<\/span>,<\/span>ans=<\/span>0<\/span>;<\/span>\n    cin>><\/span>n>><\/span>m;<\/span>\n    register<\/span> long<\/span> long<\/span> int<\/span> i;<\/span>\n    for<\/span>(<\/span>i=<\/span>1<\/span>;<\/span> i<=<\/span>m;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        cin>><\/span>l>><\/span>r>><\/span>ks>><\/span>e1;<\/span>\n        dc=<\/span>(<\/span>e1-<\/span>ks)<\/span>\/<\/span>(<\/span>r-<\/span>l)<\/span>;<\/span>\n        out[<\/span>l]<\/span>=<\/span>out[<\/span>l]<\/span>+<\/span>ks;<\/span>\n        out[<\/span>l+<\/span>1<\/span>]<\/span>=<\/span>out[<\/span>l+<\/span>1<\/span>]<\/span>+<\/span>dc-<\/span>ks;<\/span>\n        out[<\/span>r+<\/span>1<\/span>]<\/span>=<\/span>out[<\/span>r+<\/span>1<\/span>]<\/span>-<\/span>dc-<\/span>e1;<\/span>\n        out[<\/span>r+<\/span>2<\/span>]<\/span>=<\/span>out[<\/span>r+<\/span>2<\/span>]<\/span>+<\/span>e1;<\/span>\n    }<\/span>\n    for<\/span>(<\/span>i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        out[<\/span>i]<\/span>=<\/span>out[<\/span>i-<\/span>1<\/span>]<\/span>+<\/span>out[<\/span>i]<\/span>;<\/span>\n        tmp+<\/span>=<\/span>out[<\/span>i]<\/span>;<\/span>\n        ans=<\/span>ans^<\/span>tmp;<\/span>\n    }<\/span>\n    cout<<<\/span>ans<<<\/span>endl;<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n
\u8bf7\u5f00 long long\u3002<\/p>\n
\u8001\u7239\u8bf4\u8981\u7528\u9b54\u6cd5\u6253\u8d25\u9b54\u6cd5 \u2014\u2014\u2014\u2014 3edc2wsx1qaz<\/p>\n
\u4e00\u5929\uff0c\u5de8\u795e 3edc2wsx1qaz \u6b63\u5728\u68ee\u6797\u91cc\u6f2b\u6b65\uff0c\u7a81\u7136\uff0c\u4e00\u53ea\u51f6\u6076\u7684\u53cc\u5934\u5de8\u4eba\u62e6\u4f4f\u4e86\u4ed6\u3002<\/p>\n
\u53cc\u5934\u5de8\u4eba\u7684\u4e24\u4e2a\u5934\u7684\u653b\u51fb\u529b\u5206\u522b\u4e3aa,b\u3002\u5b83\u6bcf\u6b21\u53ef\u4ee5\u5bf9 3edc2wsx1qaz \u9020\u6210 |a-b| \u7684\u9b54\u6cd5\u4f24\u5bb3\u3002<\/p>\n
3edc2wsx1qaz \u89c9\u5f97\u8fd9\u53ea\u602a\u7269\u5341\u5206\u96be\u7f20\u3002<\/p>\n
\u201c\u8981\u7528\u9b54\u6cd5\u6253\u8d25\u9b54\u6cd5\uff01\u201d \u5c31\u5728\u8fd9\u65f6\uff0c\u8001\u7239\u7684\u8bdd\u56de\u54cd\u5728 3edc2wsx1qaz \u7684\u8033\u8fb9\uff0c3edc2wsx1qaz \u987f\u65f6\u611f\u5230\u4e00\u80a1\u529b\u91cf\u6d8c\u4e0a\u5fc3\u5934\uff0c\u4e8e\u662f\uff0c\u4ed6\u51b3\u5b9a\u4ece\u5b83\u7684\u7279\u6b8a\u80fd\u529b\u4e0b\u624b\uff0c\u4ece\u800c\u6253\u8d25\u5b83\u3002<\/p>\n
998244353\u5e74\u524d\uff0c\u5de8\u795e Rainy7 \u66fe\u7ecf\u6559\u8fc7\u4ed6\u540d\u4e3a \u722a\u5df4 \u7684 % \u6cd5\uff0c\u4ed6\u51b3\u5b9a\u7528\u8fd9\u79cd % \u6cd5\u51fb\u8d25\u5de8\u4eba\u3002<\/p>\n
3edc2wsx1qaz \u53ef\u4ee5\u4f7f\u7528\u65e0\u9650\u6b21\u6cd5\u672f\uff0c\u7b2ci\u6b21\u4f7f\u7528\u53ef\u4ee5\u4efb\u9009\u4e00\u4e2a\u5934\uff0c\u4f7f\u5f97\u5b83\u7684\u653b\u51fb\u529b\u589e\u52a0\u6216\u51cf\u5c11i\u3002\uff08\u5728\u6b64\u8fc7\u7a0b\u4e2d\u653b\u51fb\u529b\u53ef\u4ee5\u662f\u8d1f\u6570\uff09<\/p>\n
3edc2wsx1qaz \u4e0d\u60f3\u53d7\u5230\u4efb\u4f55\u4f24\u5bb3\uff0c\u6240\u4ee5\uff0c\u4ed6\u60f3\u77e5\u9053\uff0c\u4ed6\u81f3\u5c11\u8981\u65bd\u51e0\u6b21\u6cd5\uff0c\u624d\u80fd\u4f7f\u5f97a-b=0\u3002<\/p>\n
3edc2wsx1qaz \u53ea\u7528\u4e86114514-1919810 s\u5c31\u89e3\u51b3\u4e86\u8fd9\u4e2a\u95ee\u9898\uff0c\u4e8e\u662f\u8ba9\u60a8\u89e3\u51b3\u3002<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
\u7b2c\u4e00\u884c\u4e00\u4e2a\u6570T\uff0c\u8868\u793a\u6570\u636e\u7ec4\u6570\u3002
 \u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff0c\u4e00\u884c\u4e24\u4e2a\u6570a,b\uff0c\u4ee3\u8868\u53cc\u5934\u5de8\u4eba\u4e24\u4e2a\u5934\u7684\u653b\u51fb\u529b\u3002<\/p>\n
<\/a>\u8f93\u51fa<\/h5>\n
\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff0c\u4e00\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6700\u5c0f\u6b21\u6570\u3002<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
\u3010\u6837\u4f8b1\u3011
 3
 1 3
 11 11
 30 20
 \u3010\u6837\u4f8b2\u3011
 1
 114514 1919810<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
\u3010\u6837\u4f8b1\u3011
 3
 0
 4
 \u3010\u6837\u4f8b2\u3011
 1900<\/p>\n
<\/a>\u63d0\u793a<\/h5>\n
\u6837\u4f8b1\u89e3\u91ca\uff1a
 \u5bf9\u4e8e\u6570\u636e1\uff0c\u4e00\u79cd\u64cd\u4f5c\u6d41\u7a0b\u5982\u4e0b\uff1a1+1=2,3+2=5,2+3=5
 \u5bf9\u4e8e\u6570\u636e2\uff0c\u7531\u4e8e\u76f8\u7b49\uff0c\u6240\u4ee5\u7b54\u6848\u4e3a0\u3002
 \u5bf9\u4e8e\u6570\u636e3\uff0c\u4e00\u79cd\u64cd\u4f5c\u6d41\u7a0b\u5982\u4e0b\uff1a20+1+2+3+4=30\u3002
 \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
<\/a>\u89e3\u6790<\/h5>\n
\u5047\u8bbe\u53cc\u65b9\u7684\u8840\u91cf\u5206\u522b\u4e3aa\u548cb\uff08a\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>\n \nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    while<\/span>(<\/span>t--<\/span>)<\/span>\n    {<\/span>\n        int<\/span> a,<\/span>b;<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>a,<\/span>&<\/span>b)<\/span>;<\/span>\n        if<\/span>(<\/span>a><\/span>b)<\/span>\n            swap<\/span>(<\/span>a,<\/span>b)<\/span>;<\/span>\n        int<\/span> i;<\/span>\n        for<\/span>(<\/span>i=<\/span>1<\/span>;<\/span> a<<\/span>b||<\/span>(<\/span>a><\/span>b&&<\/span>(<\/span>a-<\/span>b)<\/span>%<\/span>2<\/span>==<\/span>1<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>\n            a+<\/span>=<\/span>i;<\/span>\n        cout<<<\/span>i-<\/span>1<\/span><<<\/span>endl;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n
\u8bf7\u5f00 long long\u3002<\/p>\n
\u82e5\u4f17\u4eba\u7686\u4e27\u6c14\uff0c\u5219\u6211\u8c12\u89c1\u8c0f\u8a00\u3002\u2014\u2014\u2014\u2014 Rainy7<\/p>\n
\u5728\u6d69\u701a\u65e0\u57a0\u7684\u5b87\u5b99\u4e2d\uff0c\u5206\u5e03\u7740\u8bb8\u8bb8\u591a\u591a\u7684\u6587\u660e\uff0c\u5b83\u4eec\u4e4b\u95f4\u7ecf\u5e38\u8d77\u51b2\u7a81\u3002<\/p>\n
\u4e00\u6b21\uff0c\u4e00\u4e2a\u6587\u660e\u6d3e\u51fa\u5927\u6279\u661f\u8230\u8fdb\u653b\u5730\u7403\uff0c\u5730\u7403\u4eba\u88ab\u6253\u5f97\u843d\u8352\u800c\u9003\u3002<\/p>\n
\u6b64\u65f6\u5728\u5730\u7403\u4e0a\uff0c\u5de8\u795e Rainy7 \u5929\u5929\u540a\u6253\u96c6\u8bad\u961f\uff0c\u5df2\u7ecf\u611f\u5230\u538c\u70e6\u4e86\uff0c\u4e8e\u662f\uff0cRainy7 \u4fbf\u53bb\u540a\u6253\u5916\u661f\u4eba\u4e86\u3002<\/p>\n
Rainy7 \u4f7f\u7528\u9b54\u6cd5\uff0c\u5c06\u8fd9n\u8258\u661f\u8230\u5c01\u9501\u4f4f\u4e86\u3002\u7136\u800c\uff0c\u8fd9\u4e9b\u661f\u8230\u90fd\u6709\u62a4\u76fe\u4fdd\u62a4\uff0cRainy7 \u8981\u60f3\u65b9\u8bbe\u6cd5\u7834\u9664\u5b83\u4eec\u3002<\/p>\n
\u661f\u8230\u7684\u5c01\u9501\u5173\u7cfb\u53ef\u4ee5\u770b\u6210\u4e00\u68f5\u6811\u3002\u4e00\u5f00\u59cb\uff0c Rainy7 \u53ef\u4ee5\u4efb\u9009\u4e00\u8258\u661f\u8230\uff0c\u7136\u540e\u76f4\u63a5\u89e3\u9664\u5b83\u7684\u62a4\u76fe\u3002\u7d27\u63a5\u7740\uff0cRainy7 \u53ef\u4ee5\u8fdb\u884cn\u6b21\u64cd\u4f5c\uff0c\u6bcf\u6b21\u9009\u62e9\u4e00\u8258\u672a\u88ab\u62a4\u76fe\u4fdd\u62a4\u7684\u661f\u8230\uff0c\u7136\u540e\u76f4\u63a5\u6467\u6bc1\u5b83\uff0c\u5e76\u4e14\u83b7\u5f97\u5b83\u88ab\u6467\u6bc1\u524d\u6240\u5728\u7684\u5168\u90fd\u662f\u672a\u88ab\u6467\u6bc1\u7684\u661f\u8230\u7684\u8fde\u901a\u5757\u7684\u5927\u5c0f\u7684\u9b54\u6cd5\u503c\u3002\u4e00\u8258\u661f\u8230\u88ab\u6467\u6bc1\u540e\uff0c\u4e0e\u5b83\u76f4\u63a5\u76f8\u8fde\u4e14\u672a\u88ab\u6467\u6bc1\u7684\u661f\u8230\u7684\u62a4\u76fe\u4f1a\u5168\u90e8\u88ab\u89e3\u9664\u3002<\/p>\n
Rainy7 \u60f3\u77e5\u9053\uff0c\u81ea\u5df1\u6700\u591a\u80fd\u83b7\u5f97\u591a\u5c11\u9b54\u6cd5\u503c\u3002\u5979\u53ea\u7528\u4e86114514-1919810s\u5c31\u89e3\u51b3\u4e86\u95ee\u9898\uff0c\u4e8e\u662f\u628a\u95ee\u9898\u629b\u7ed9\u4e86\u60a8\u3002
 \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
\u5982\u56fe\u6240\u793a\uff0c\u52a0\u7c97\u7684\u661f\u8230\u8868\u793a\u5df2\u7ecf\u88ab\u6467\u6bc1\u3002\u82e5\u9009\u62e92\u53f7\u661f\u8230\uff0c\u5c06\u4f1a\u83b7\u5f974\u70b9\u9b54\u6cd5\u503c\uff0c\u5e76\u4e14\u89e3\u96643,5,6\u7684\u62a4\u76fe\u3002\u82e5\u9009\u62e99\u53f7\u661f\u8230\uff0c\u5c06\u4f1a\u83b7\u5f973\u70b9\u9b54\u6cd5\u503c\uff0c\u5e76\u4e14\u89e3\u96647,8\u7684\u62a4\u76fe\u3002<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
\u7b2c\u4e00\u884c\u4e00\u4e2a\u6570n\uff0c\u8868\u793a\u661f\u8230\u6570\u91cf\u3002
 \u63a5\u4e0b\u6765n-1\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u6570u,v\uff0c\u8868\u793a\u661f\u8230\u7684\u76f8\u8fde\u5173\u7cfb\u3002<\/p>\n
<\/a>\u8f93\u51fa<\/h5>\n
\u4e00\u884c\u4e00\u4e2a\u6570\uff0c\u8868\u793a\u6700\u591a\u80fd\u83b7\u5f97\u7684\u9b54\u6cd5\u503c\u3002<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
\u3010\u6837\u4f8b1\u3011
 9
 1 2
 2 3
 2 5
 2 6
 1 4
 4 9
 9 7
 9 8
 \u3010\u6837\u4f8b2\u3011
 5
 1 2
 1 3
 2 4
 2 5<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
\u3010\u6837\u4f8b1\u3011
 36
 \u3010\u6837\u4f8b2\u3011
 14<\/p>\n
<\/a>\u63d0\u793a<\/h5>\n
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
<\/a>\u89e3\u6790<\/h5>\n
\u6811\u5f62DP\uff0c\u5148\u6c42\u51fa1\u70b9\u7684\u9b54\u6cd5\u503c\uff0c\u540e\u7ecf\u8fc7\u72b6\u6001\u8f6c\u79fb\u6c42\u51fa\u5176\u4ed6\u70b9\u7684\u9b54\u6cd5\u503c\uff0c\u6c42\u6700\u5927\u503c\u5373\u53ef\u3002<\/p>\n
#include<\/span><\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nvector<<\/span>ll><\/span>w[<\/span>300500<\/span>]<\/span>;<\/span>\nint<\/span> vis[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> vis1[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll size1[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll ans[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll n;<\/span>\nll dfs<\/span>(<\/span>ll k)<\/span>\n{<\/span>\n    if<\/span>(<\/span>size1[<\/span>k]<\/span>!=<\/span>0<\/span>)<\/span>\n        return<\/span> size1[<\/span>k]<\/span>;<\/span>\n    size1[<\/span>k]<\/span>=<\/span>1<\/span>;<\/span>\n    vis[<\/span>k]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>0<\/span>;<\/span>i<<\/span>w[<\/span>k]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>!<\/span>vis[<\/span>w[<\/span>k]<\/span>[<\/span>i]<\/span>]<\/span>)<\/span>\n        {<\/span>\n            size1[<\/span>k]<\/span>+<\/span>=<\/span>dfs<\/span>(<\/span>w[<\/span>k]<\/span>[<\/span>i]<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> size1[<\/span>k]<\/span>;<\/span>\n}<\/span>\nll dfs1<\/span>(<\/span>ll k)<\/span>\n{<\/span>\n    vis1[<\/span>k]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>0<\/span>;<\/span>i<<\/span>w[<\/span>k]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>!<\/span>vis1[<\/span>w[<\/span>k]<\/span>[<\/span>i]<\/span>]<\/span>)<\/span>\n        {<\/span>\n            ll x=<\/span>w[<\/span>k]<\/span>[<\/span>i]<\/span>;<\/span>\n            ans[<\/span>x]<\/span>=<\/span>ans[<\/span>k]<\/span>+<\/span>(<\/span>n-<\/span>size1[<\/span>x]<\/span>-<\/span>1<\/span>)<\/span>-<\/span>(<\/span>size1[<\/span>x]<\/span>-<\/span>1<\/span>)<\/span>;<\/span>\n            dfs1<\/span>(<\/span>x)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>n)<\/span>;<\/span>\n    ll x,<\/span>y;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span>i<=<\/span>n-<\/span>1<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%lld%lld\"<\/span>,<\/span>&<\/span>x,<\/span>&<\/span>y)<\/span>;<\/span>\n        w[<\/span>x]<\/span>.<\/span>push_back<\/span>(<\/span>y)<\/span>;<\/span>\n        w[<\/span>y]<\/span>.<\/span>push_back<\/span>(<\/span>x)<\/span>;<\/span>\n    }<\/span>\n    dfs<\/span>(<\/span>1<\/span>)<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        ans[<\/span>1<\/span>]<\/span>+<\/span>=<\/span>size1[<\/span>i]<\/span>;<\/span>\n    }<\/span>\n    dfs1<\/span>(<\/span>1<\/span>)<\/span>;<\/span>\n    ll max1=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        max1=<\/span>max<\/span>(<\/span>max1,<\/span>ans[<\/span>i]<\/span>)<\/span>;<\/span>\n    }<\/span>\n    cout<<<\/span>max1<<<\/span>endl;<\/span>\n    return<\/span> 0<\/span>;<\/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-29","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\/29","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=29"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/29\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
http:\/\/icpc.upc.edu.cn\/problem.php?cid=2535&pid=6<\/a><\/p>\n
http:\/\/icpc.upc.edu.cn\/problem.php?cid=2535&pid=5<\/a><\/p>\n