\u5927\u6982\u5408\u5e76\u7684\u7ebf\u6bb5\u6811\u8fd8\u662f\u53ef\u4ee5\u4f7f\u7528pbds\u91cc\u9762\u7684\u5e73\u8861\u6811\u6765\u4ee3\u66ff\uff0c\u4f46\u662f\u6211\u5199\u4ee3\u7801\u4e4b\u524d\u5e76\u4e0d\u77e5\u9053\u2026\u2026<\/p>\n\n\n\n
\u5199\u5b8c\u4e4b\u540e\u53bb\u8bfb\u4e86\u6700\u77ed\u7684\u4ee3\u7801\uff08\u4ee3\u7801\u957f\u5ea60.5\u500d\uff09\uff0c\u53d1\u73b0\u662f\u4e2d\u56fd\u9009\u624b\u3002\u6ca1\u8bfb\u61c2\uff0c\u95ee\u51fa\u9898\u4eba\uff0c\u51fa\u9898\u4eba\u4e5f\u8bfb\u4e0d\u61c2\u3002\u3002<\/p>\n\n\n\n
\u627e\u5230\u4ed6\u7684QQ\u5c31\u95ee\u4e86\u4e00\u4e0b\u4ed6\uff0c\u7136\u540e\u53d1\u73b0\u4e86\u4e00\u4e2a\u5f88\u5999\u7684\u505a\u6cd5\uff0c\u7136\u540e\u53d1\u73b0\u597d\u591a\u9009\u624b\u90fd\u662f\u5199\u7684\u8fd9\u4e2a\u505a\u6cd5\uff0c\u53ea\u6709\u6211\u592a\u61a8\u4e86\u53bb\u5b9e\u73b0\u9898\u89e3\u3002\u3002\u3002\u4e0b\u9762\u63cf\u8ff0\u4e00\u4e0b\u90a3\u4e2a\u505a\u6cd5\u3002<\/p>\n\n\n\n
\u9996\u5148\u8fdb\u884c\u4e00\u6b65\u8f6c\u5316\u3002<\/p>\n\n\n\n
\u4e00\u4e2a\u6811\u4e0a\u7684\u8def\u5f84\uff0c[|\u8def\u5f84|>=k] = #\u957f\u5ea6\u4e3ak\u7684\u5b50\u6bb5-#\u957f\u5ea6\u4e3ak+1\u7684\u5b50\u6bb5<\/p>\n\n\n\n
\u56e0\u6b64\u53ea\u9700\u8981\u5bf9\u6811\u4e0a\u7684\u6240\u6709\u957f\u5ea6\u4e3ak\u6216\u8005k+1\u7684\u8def\u5f84\u6c42\u4e00\u4e0b\u88ab\u8986\u76d6\u4e86\u591a\u5c11\u6b21\uff0c\u5c31\u5f97\u5230\u7b54\u6848\u3002\u6bd4\u5982\u88ab\u8986\u76d6\u4e86c\u6b21\uff0c\u90a3\u4e48\u8d21\u732e\u7684\u7edd\u5bf9\u503c\u5c31\u662fc(c-1)\/2\uff0c\u7b26\u53f7\u53d6\u51b3\u4e8e\u957f\u5ea6\u662fk(\u6b63)\u8fd8\u662fk+1(\u8d1f)\u3002<\/p>\n\n\n\n
\u9996\u5148\u8fdb\u884c\u91cd\u94fe\u5256\u5206\uff0c\u7136\u540e\u5bf9\u4e8e\u4e00\u6761\u8def\u5f84\uff0c\u957f\u5ea6\u4e3ak\u7684\u6bb5\u5927\u6982\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n\n\n\n \u7ad6\u76f4\u7684\u8986\u76d6\u7684\u6bb5\u4e0a\u7684\u8d21\u732e\u53ef\u4ee5\u76f4\u63a5\u4f7f\u7528\u5256\u5206\u4e0a\u7684\u5dee\u5206\u6765\u505a\u3002\u73b0\u5728\u95ee\u9898\u5c31\u51fa\u5728\u62d0\u5f2f\u7684\u6bb5\u4e0a\u3002<\/p>\n\n\n\n \u62d0\u5f2f\u7684\u6bb5\u7684\u5904\u7406\u5f88\u5de7\u5999\uff0c\u8003\u8651\u6211\u4eec\u628a\u6574\u4e2a\u533a\u95f4\u62c6\u5206\u6210\u91cd\u94fe\u4e0a\u3002<\/p>\n\n\n\n \u7136\u540e\u8003\u8651\u4efb\u4f55\u4e00\u4e2a\u957f\u5ea6\u4e3ak\u7684\u8de8\u8d8alca(4\u53f7\u70b9)\u7684\u5b50\u6bb5\uff0c\u6211\u4eec\u91c7\u7528\u4ed6\u5f00\u59cb\u8282\u70b9\u6240\u5728\u91cd\u94fe\u3001\u7ec8\u6b62\u8282\u70b9\u6240\u5728\u91cd\u94fe\u3001\u5f00\u59cb\u8282\u70b9\u7684\u6df1\u5ea6\u6765\u5dee\u5206\u8bb0\u5f55\uff0c\u5f00\u4e00\u4e2a\u6570\u7ec4\u5957map\u5957map\u5c31\u884c\u4e86\uff0c\u590d\u6742\u5ea6\u4e5f\u662f\u4e24\u4e2alog\u2026\u2026\u592a\u5999\u4e86\u3002<\/p>\n\n\n\n \u4e0b\u9762\u662f\u6211\u7684\u9898\u89e3\u505a\u6cd5\u4ee3\u7801<\/p>\n\n\n\n \u4e0b\u9762\u662f\u9ad8\u6c34\u5e73\u9009\u624b\u7684nb\u505a\u6cd5\u4ee3\u7801<\/p>\n\n\n\n \u4e00\u53e5\u8bdd\u9898\u610f\uff1a\u7ed9\u4f60\u4e00\u68f5n\u4e2a\u70b9\u7684\u6811\uff0c\u548c\u6811\u4e0a\u7684m\u6761\u8def\u5f84\u3002\u95ee\u6709\u591a\u5c11\u5bf9\u8def\u5f84\u7684\u4ea4\u957f\u5ea6\u5927\u4e8ek? n m 150000, 4s<\/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":[23,22,24],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/344"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=344"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/344\/revisions"}],"predecessor-version":[{"id":347,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/344\/revisions\/347"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"\"](\"http:\/\/nocriz.com\/wp-content\/uploads\/2020\/04\/image.png\")
![\"\"](\"http:\/\/nocriz.com\/wp-content\/uploads\/2020\/04\/image-1.png\")
#pragma comment(linker, \"\/stack:200000000\")\n#pragma GCC optimize(\"Ofast,no-stack-protector\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native\")\n#pragma GCC optimize(\"unroll-loops\")\n#include <bits\/stdc++.h>\n\n\nusing namespace std;\n#define set0(x) memset(x,0,sizeof(x))\n#define F first\n#define S second\n#define PB push_back\n#define MP make_pair\n#define rep(i, a, b) for(int i = a; i < (b); ++i)\n#define trav(a, x) for(auto& a : x)\n#define all(x) x.begin(), x.end()\n#define sz(x) (int)(x).size()\n\ntypedef long long ll;\ntypedef pair<int,int> pii;\ntypedef pair<ll,ll> pll;\ntypedef vector<int> VI;\ntemplate<typename T> void read(T &x){\n x = 0;char ch = getchar();ll f = 1;\n while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}\n while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;\n}\ntemplate<typename T, typename... Args> void read(T &first, Args& ... args) {\n read(first);\n read(args...);\n}\n\n\nconst int N = 150050;\nint n,m,k,s[N],t[N],lc[N],u,v;\nvector<int> G[N],G2[N],T[N],oT[N];\n\nint fa[N][19],d[N],dfn[N],sz[N],tim = 0;\nvoid dfs0(int num,int cf = 0){\n dfn[num] = ++tim;\n fa[num][0] = cf;\n sz[num] = 1;\n for(int j=0;fa[num][j];j++)fa[num][j+1] = fa[fa[num][j]][j];\n for(auto ct:G[num]){\n if(ct==cf)continue;\n d[ct] = d[num]+1;\n dfs0(ct,num);\n sz[num]+=sz[ct];\n }\n}\n\ninline int lca(int u,int v){\n if(d[u]<d[v])swap(u,v);\n for(int i=18;i>=0;i--)if(fa[u][i] && d[fa[u][i]]>=d[v])u = fa[u][i];\n for(int i=18;i>=0;i--)if(fa[u][i]!=fa[v][i])u = fa[u][i],v = fa[v][i];\n return u == v?u:fa[u][0];\n}\n\ninline int anc(int u,int x){\n for(int i=18;i>=0;i--) if(fa[u][i] && d[fa[u][i]]>=x)u = fa[u][i];\n return u;\n}\n\nstruct Fenwick{\n int s[N];\n vector<pii> log;\n inline void update(int pos, int dif) {\n log.emplace_back(pos,dif);\n while(pos<N){\n s[pos]+=dif;\n pos+=pos&(-pos);\n }\n }\n void reset(){\n int pos,dif;\n for(auto ct:log){\n pos = ct.F;\n dif = -ct.S;\n while(pos<N){\n s[pos]+=dif;\n pos+=pos&(-pos);\n }\n }\n log.clear();\n }\n inline int query(int pos) {\n int res = 0;\n while(pos){\n res+=s[pos];\n pos-=pos&(-pos);\n }\n return res;\n }\n}A;\n\nvector<pii> F[N],F2[N];\n\nstruct node{\n int ls = 0,rs = 0;\n int val = 0;\n}nds[10000010];\nint cnt = 0,rts[N];\n#define mid ((cl+cr)\/2)\nint query(int id,int l,int r,int cl = 0,int cr = n){\n if(id == 0 || (l<=cl && cr<=r))return nds[id].val;\n return ((l<=mid)?query(nds[id].ls,l,r,cl,mid):0)+((r>mid)?query(nds[id].rs,l,r,mid+1,cr):0);\n}\nvoid add(int &id,int x,int cl = 0,int cr = n){\n if(!id)id = ++cnt;nds[id].val++;if(cl == cr)return;\n if(x<=mid)\n add(nds[id].ls,x,cl,mid);\n else\n add(nds[id].rs,x,mid+1,cr);\n}\nint merge(int a,int b){\n if(!a || !b)return a|b;\n nds[a].val+=nds[b].val;\n nds[a].ls = merge(nds[a].ls,nds[b].ls);\n nds[a].rs = merge(nds[a].rs,nds[b].rs);\n return a;\n}\n\nvoid reset(){\n memset(nds,0,sizeof(nds[0])*(cnt+1));\n cnt = 0;\n}\nll ans = 0;\n\nint crt = 0;\nvoid dfs1(int num){\n int tgt;\n auto add_it = [&](int ct){\n if(d[num]+d[ct]-2*d[crt]>=k){\n if(d[num]>=d[crt]+k){\n tgt = anc(num,d[num]-k+1);\n ans+=nds[rts[num]].val;\n ans-=query(rts[num],dfn[tgt],dfn[tgt]+sz[tgt]-1);\n }else{\n tgt = anc(ct,d[crt]+k-(d[num]-d[crt]));\n ans +=query(rts[num],dfn[tgt],dfn[tgt]+sz[tgt]-1);\n }\n }\n };\n int mx = -1,ms = -1;\n for(auto ech:G2[num]){\n dfs1(ech);\n if((int)T[ech].size()>mx){\n mx = T[ech].size();\n ms = ech;\n }\n }\n if(ms!=-1)rts[num] = merge(rts[num],rts[ms]);\n for(auto ct:T[num]){\n add_it(ct);\n add(rts[num],dfn[ct]);\n }\n if(ms!=-1){\n \/\/cout<<ms<<endl;\n swap(T[num],T[ms]);\n for(auto ct:T[ms])T[num].PB(ct);\n }\n for(auto ech:G2[num]){\n if(ech == ms){\n \/\/cout<<\"JMP\"<<endl;\n continue;\n }\n for(auto ct:T[ech]){\n add_it(ct);\n T[num].PB(ct);\n }\n rts[num] = merge(rts[num],rts[ech]);\n }\n}\n\nint main() {\n read(n,m,k);\n for(int i=1;i<n;i++){\n read(u,v);\n G[u].PB(v);\n G[v].PB(u);\n }\n d[1] = 1;\n dfs0(1);\n for(int i=0;i<m;i++){\n read(s[i],t[i]);\n if(dfn[s[i]]>dfn[t[i]])swap(s[i],t[i]);\n lc[i] = lca(s[i],t[i]);\n F[d[lc[i]]].emplace_back(s[i],t[i]);\n F2[lc[i]].emplace_back(s[i],t[i]);\n }\n for(int i=n;i>=1;i--){\n for(auto ct:F[i]){\n int l = ct.F,r = ct.S;\n ans+=A.query(dfn[l]);\n ans+=A.query(dfn[r]);\n }\n for(auto ct:F[i]){\n int l = ct.F,r = ct.S;\n if(d[l]>=i+k){\n l = anc(l,i+k);\n A.update(dfn[l],1);\n A.update(dfn[l]+sz[l],-1);\n }\n if(d[r]>=i+k){\n r = anc(r,i+k);\n A.update(dfn[r],1);\n A.update(dfn[r]+sz[r],-1);\n }\n }\n }\n A.reset();\n auto cmp = [&](int a,int b)->bool{return dfn[a]<dfn[b];};\n for(int i=1;i<=n;i++){\n crt = i;\n vector<int> cu,scope;\n scope.PB(i);\n for(auto ct:F2[i]){\n cu.PB(ct.F);\n T[ct.F].PB(ct.S);\n oT[ct.F].PB(ct.S);\n }\n sort(all(cu),cmp);\n cu.erase(unique(all(cu)),cu.end());\n vector<int> stk;\n stk.PB(i);\n rts[i] = ++cnt;\n auto pb = [&](int a){\n rts[a] = ++cnt;\n scope.PB(a);\n stk.PB(a);\n };\n for(auto ct:cu){\n int dd = lca(ct,stk.back());\n while(d[stk.back()]>d[dd]){\n if(d[stk[stk.size()-2]]>d[dd]) G2[stk[stk.size()-2]].PB(stk.back());\n else G2[dd].PB(stk.back());\n stk.pop_back();\n }\n if(d[stk.back()]<d[dd]) pb(dd);\n if(d[stk.back()]<d[ct]) pb(ct);\n }\n while(stk.size()>=2){\n G2[stk[stk.size()-2]].PB(stk.back());\n stk.pop_back();\n }\n dfs1(i);\n for(auto ct:cu){\n ans+=1ll*A.query(dfn[ct])*oT[ct].size();\n for(auto ed:oT[ct]){\n if(d[ed]>=d[i]+k){\n int cc = anc(ed,d[i]+k);\n A.update(dfn[cc],1);\n A.update(dfn[cc]+sz[cc],-1);\n }\n }\n }\n A.reset();\n reset();\n for(auto ct:scope){\n G2[ct].clear();\n rts[ct] = 0;\n T[ct].clear();\n oT[ct].clear();\n }\n }\n cout<<ans<<endl;\n return 0;\n}\n<\/code><\/pre>\n\n\n\n#include<bits\/stdc++.h>\n \nusing namespace std;\n \ntypedef long long LL;\n#define N 300000\n \nint n,m,k,a[N][2],fa[N],sz[N],top[N],d[N],prf[N],f1[N],q1[N],q2[N];\nvector<int> g[N],b[N];\nmap<int,map<int,int> > f2[N];\nLL ans;\n \nvoid dfs1(int u){\n\td[u]=d[fa[u]]+1;\n\tsz[u]=1;\n\tfor (int v:g[u])\n\t\tif (v!=fa[u]){\n\t\t\tfa[v]=u;\n\t\t\tdfs1(v);\n\t\t\tsz[u]+=sz[v];\n\t\t}\n}\n \nvoid dfs2(int u){\n\tif (!top[u]) top[u]=u;\n\tb[top[u]].push_back(u);\n\tint t=0;\n\tfor (int v:g[u])\n\t\tif (v!=fa[u]&&sz[v]>sz[t]) t=v;\n\tif (!t) return;\n\tprf[u]=t; top[t]=top[u]; dfs2(t);\n\tfor (int v:g[u])\n\t\tif (v!=fa[u]&&v!=t) dfs2(v);\n}\n \nint lca(int x,int y){\n\tfor (;top[x]!=top[y];x=fa[top[x]])\n\t\tif (d[top[x]]<d[top[y]]) swap(x,y);\n\treturn d[x]<d[y]?x:y;\n}\n \nint go(int x,int k){\n\tint len=d[x]-d[top[x]];\n\tif (len<k) return go(fa[top[x]],k-len-1);\n\treturn b[top[x]][len-k];\n}\n \nint add1(int x,int y){\n\tint len=d[x]-d[y];\n\tif (len<k) return x;\n\tint z=go(x,len-k+1);\n\t++f1[x]; --f1[z];\n\treturn z;\n}\n \nvoid add2(int u1,int u2,int v1,int v2){\n\tif (top[u1]>top[v1]){\n\t\tswap(u1,v1); swap(u2,v2);\n\t}\n\tif (d[u1]>d[u2]) swap(u1,u2);\n\t++f2[top[u1]][top[v1]][d[u1]];\n\t--f2[top[u1]][top[v1]][d[u2]+1];\n}\n \nvoid add(int x,int y){\n\tint z=lca(x,y);\n\tx=add1(x,z); y=add1(y,z);\n\tint u=x,v=y;\n\tint n1=0,n2=0;\n\tfor (;top[u]!=top[z];u=fa[top[u]]) q1[++n1]=u;\n\tfor (;top[v]!=top[z];v=fa[top[v]]) q2[++n2]=v;\n\tif (u!=z) q1[++n1]=u; if (v!=z) q2[++n2]=v;\n\tfor (int i1=1,i2=n2;i1<=n1;++i1){\n\t\tint u1=q1[i1],u2=top[u1];\n\t\tif (d[u2]<=d[z]) u2=prf[z];\n\t\tfor (;i2;--i2){\n\t\t\tint v1=q2[i2],v2=top[v1];\n\t\t\tif (d[v2]<=d[z]) v2=prf[z];\n\t\t\tif (d[u1]+d[v1]-d[z]*2<k) continue;\n\t\t\tint len=d[u1]+d[v1]-d[z]*2;\n\t\t\tint w1=go(v1,len-k),w2=0;\n\t\t\tlen=d[u2]+d[v1]-d[z]*2;\n\t\t\tif (len>=k){\n\t\t\t\tw2=go(v1,len-k);\n\t\t\t\tadd2(u1,u2,w1,w2);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tlen=d[u1]+d[v1]-d[z]*2;\n\t\t\tw2=go(u1,len-k);\n\t\t\tadd2(u1,w2,w1,v1);\n\t\t\tu1=fa[w2];\n\t\t}\n\t}\n}\n \nLL C(LL x){return x*(x-1)\/2;}\n \nvoid dfs3(int u,int t){\n\tfor (int v:g[u])\n\t\tif (v!=fa[u]){\n\t\t\tdfs3(v,t);\n\t\t\tf1[u]+=f1[v];\n\t\t}\n\tans+=C(f1[u])*t;\n}\n \nvoid calc(int t){\n\tfor (int i=1;i<=n;++i){\n\t\tfor (auto j:f2[i]){\n\t\t\tLL sum=0,lst=0;\n\t\t\tfor (auto k:j.second){\n\t\t\t\tans+=(k.first-lst)*C(sum)*t;\n\t\t\t\tlst=k.first;\n\t\t\t\tsum+=k.second;\n\t\t\t}\n\t\t}\n\t\tf2[i].clear();\n\t}\n}\n \nint main(){\n\tscanf(\"%d%d%d\",&n,&m,&k);\n\tfor (int i=1;i<n;++i){\n\t\tint x,y; scanf(\"%d%d\",&x,&y);\n\t\tg[x].push_back(y); g[y].push_back(x);\n\t}\n\tdfs1(1); dfs2(1);\n\tfor (int i=1;i<=m;++i){\n\t\tscanf(\"%d%d\",a[i]+0,a[i]+1);\n\t\tadd(a[i][0],a[i][1]);\n\t}\n\tdfs3(1,1); calc(1);\n\tmemset(f1,0,sizeof f1);\n\t++k;\n\tfor (int i=1;i<=m;++i)\n\t\tadd(a[i][0],a[i][1]);\n\tdfs3(1,-1); calc(-1);\n\tprintf(\"%lld\\n\",ans);\n\t\n\treturn 0;\n}<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"