題目描述

小c同學認為跑步非常有趣,于是決定制作一款叫做《天天愛跑步》的游戲。?天天愛跑步?是一個養成類游戲,需要玩家每天按時上線,完成打卡任務。

這個游戲的地圖可以看作一一棵包含?$n$個結點和?$n?1$條邊的樹, 每條邊連接兩個結點,且任意兩個結點存在一條路徑互相可達。樹上結點編號為從$1$到$n$的連續正整數。

現在有$m$個玩家,第$i$個玩家的起點為?S_iS?i??,終點為?T_iT?i???。每天打卡任務開始時,所有玩家在第$0$秒同時從自己的起點出發, 以每秒跑一條邊的速度, 不間斷地沿著最短路徑向著自己的終點跑去, 跑到終點后該玩家就算完成了打卡任務。 (由于地圖是一棵樹, 所以每個人的路徑是唯一的)

小C想知道游戲的活躍度, 所以在每個結點上都放置了一個觀察員。 在結點$j$的觀察員會選擇在第W_jW?j??秒觀察玩家, 一個玩家能被這個觀察員觀察到當且僅當該玩家在第W_jW?j??秒也理到達了結點?$j$?。 小C想知道每個觀察員會觀察到多少人?

注意: 我們認為一個玩家到達自己的終點后該玩家就會結束游戲, 他不能等待一 段時間后再被觀察員觀察到。 即對于把結點$j$作為終點的玩家: 若他在第W_jW?j??秒重到達終點,則在結點$j$的觀察員不能觀察到該玩家;若他正好在第W_jW?j??秒到達終點,則在結點$j$的觀察員可以觀察到這個玩家。

輸入輸出格式

輸入格式：

第一行有兩個整數$n$和$m$?。其中$n$代表樹的結點數量, 同時也是觀察員的數量,?$m$代表玩家的數量。

接下來?$n?1$行每行兩個整數$u$和?$v$,表示結點?$u$到結點?$v$有一條邊。

接下來一行?$n$個整數,其中第$j$個整數為W_jW?j???, 表示結點$j$出現觀察員的時間。

接下來?$m$行,每行兩個整數S_iS?i??,和T_iT?i??,表示一個玩家的起點和終點。

對于所有的數據,保證1\leq S_i,T_i\leq n, 0\leq W_j\leq n1≤S?i??,T?i??≤n,0≤W?j??≤n?。

輸出格式：

輸出1行?$n$個整數,第$j$個整數表示結點$j$的觀察員可以觀察到多少人。

輸入輸出樣例

輸入樣例#1：
6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6 輸出樣例#1：
2 0 0 1 1 1 輸入樣例#2：
5 3 1 2 2 3 2 4 1 5 0 1 0 3 0 3 1 1 4 5 5 輸出樣例#2：
1 2 1 0 1

說明

【樣例1說明】

對于1號點，W_i=0W?i??=0，故只有起點為1號點的玩家才會被觀察到，所以玩家1和玩家2被觀察到，共有2人被觀察到。

對于2號點，沒有玩家在第2秒時在此結點，共0人被觀察到。

對于3號點，沒有玩家在第5秒時在此結點，共0人被觀察到。

對于4號點，玩家1被觀察到，共1人被觀察到。

對于5號點，玩家1被觀察到，共1人被觀察到。

對于6號點，玩家3被觀察到，共1人被觀察到。

【子任務】

每個測試點的數據規模及特點如下表所示。 提示: 數據范圍的個位上的數字可以幫助判斷是哪一種數據類型。

【提示】

如果你的程序需要用到較大的棧空問 (這通常意味著需要較深層數的遞歸), 請務必仔細閱讀選手日錄下的文本當rumung:/stact.p″, 以了解在最終評測時?？諉柕南拗婆c在當前工作環境下調整?？諉栂拗频姆椒?。

在最終評測時，調用棧占用的空間大小不會有單獨的限制，但在我們的工作

環境中默認會有 8 MB 的限制。 這可能會引起函數調用層數較多時， 程序發生

棧溢出崩潰。

我們可以使用一些方法修改調用棧的大小限制。 例如， 在終端中輸入下列命

令 ulimit -s 1048576

此命令的意義是，將調用棧的大小限制修改為 1 GB。

例如，在選手目錄建立如下 sample.cpp 或 sample.pas

將上述源代碼編譯為可執行文件 sample 后，可以在終端中運行如下命令運

行該程序

./sample

如果在沒有使用命令“ ulimit -s 1048576”的情況下運行該程序， sample

會因為棧溢出而崩潰； 如果使用了上述命令后運行該程序，該程序則不會崩潰。

特別地， 當你打開多個終端時， 它們并不會共享該命令， 你需要分別對它們

運行該命令。

請注意， 調用棧占用的空間會計入總空間占用中， 和程序其他部分占用的內

存共同受到內存限制。

題解

一個晚上，三個多小時，終于把NOIP最難一題拿下，時隔一年，NOIP2016全滿AK

25分算法

直接暴力，跟著人走，當發現當前節點滿足條件就統計

S為根節點部分分

S為根節點，如果節點i可以觀測到人，那么首先要滿足w[i]==deep[i]，然后以i為根節點的子樹包含多少個終點，i節點的答案就是幾

T為根節點

對于i節點，深度為deep[i]+w[i]的起點才會產生貢獻。那就dfs樹上統計唄： 1、開一個桶bac[x]表示當前深度為x的起點有多少個 2、對于節點i，訪問時先記錄當時的bac[deep[i]+w[i]]，再往下遞歸，遞歸完后檢查bac[deep[i]+w[i]]，增加了v就說明它的子樹有v個這樣的起點，i的答案就是v

退化為鏈部分分

退化為鏈你能想到什么？ 所有的路徑要么左走要么右走 我們只考慮左走【右走類似】 右走時，對于節點i，只有節點i-w[i]為起點時才會產生貢獻。 那就向右掃一遍： 1、同樣開一個桶bac[x]表示掃到現在以x為起點的還未走完的路徑有多少個 2、記錄當前點i的答案bac[i-w[i]] 3、對于在該點結束的路徑的bac[S]--

滿分算法

滿分算法其實就是綜上所述。。 先把樹進行lca，路徑分為向上和向下走
1、對于向上走的路徑，在i節點，當deep[i]+w[i]==deep[S]時才會產生貢獻 借用以T為根節點的思想，開一個桶來差分統計就好了
2、對于向下走的路徑，在i節點，當deep[i]-w[i]==deep[T]-dis[S,T]-pret[T]時才會產生貢獻【dis表示路徑長，pret表示若該路徑起點為lca,則走到lca時是什么時刻，若該路徑起點為自然起點，則pret=0】
3、進行同樣的統計，到i節點時把向上路徑的起點S_up和向下路徑的終點T_up【起點在上面的終點】的對應的bac[ ]++【例如T_up就是bac[deep[T]-dis[S,T]-pret[T]]++】，在訪問結束時將向下路徑的起點S_down和向上路徑的終點T_up對應的另一個端點的統計撤銷【類似于鏈狀部分分的算法，看不明白可以參照一下】
4、若該點為lca且該點產生了貢獻，貢獻值應該-1，因為統計了兩次

總的來說要注意的地方還是很多的，細節處理要特別注意，3個小時終于A了QAQ，膜拜那些考場AK的dalao ?orzorz
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #define LL long long int using namespace std; const int maxn=700005,maxm=2000100,INF=2000000000,P=1000000007; //快速讀入 inline int read(){int out=0,flag=1;char c=getchar();while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}while(c>=48&&c<=57){out=out*10+c-48;c=getchar();}return out*flag; } //邊信息建立 int head[maxn],nedge=0; struct EDGE{int to,next; }edge[maxm];inline void build(int a,int b){edge[nedge]=(EDGE){b,head[a]};head[a]=nedge++;edge[nedge]=(EDGE){a,head[b]};head[b]=nedge++; } //lca詢問信息建立 int Head[maxn],nlca=0; struct LCA{int to,flag,next; }Lca[maxm];inline void link(int a,int b){Lca[nlca]=(LCA){b,0,Head[a]};Head[a]=nlca++;Lca[nlca]=(LCA){a,0,Head[b]};Head[b]=nlca++; }int N,M,w[maxn],rt=0,Siz[maxn],disrt=INF; //數據讀入 void init(){fill(head,head+maxn,-1);fill(Head,Head+maxn,-1);N=read();M=read();int a,b;for(int i=1;i<N;i++) build(read(),read());for(int i=1;i<=N;i++) w[i]=read();for(int i=1;i<=M;i++){a=read();b=read();link(a,b);} } //重心為根 void dfs1(int u,int f){int to,Min=INF,Max=-INF;Siz[u]=1;for(int k=head[u];k!=-1;k=edge[k].next)if((to=edge[k].to)!=f){dfs1(to,u);Siz[u]+=Siz[to];if(Siz[to]<Min) Min=Siz[to];if(Siz[to]>Max) Max=Siz[to];}if(Min==INF) return;if(N-Siz[u]<Min&&f) Min=N-Siz[u];if(N-Siz[u]>Max) Max=N-Siz[u];if(Max-Min<disrt){disrt=Max-Min;rt=u;} }void focus(){dfs1(1,0);if(!rt) rt=1;//cout<<rt<<endl; }vector<int> Su[maxn],Sd[maxn],Tu[maxn],Td[maxn]; int pre[maxn],dep[maxn],dis[maxn],S[maxn],T[maxn],pret[maxn],pathi=0,temp; int lca0[maxn]; bool vis[maxn];inline int find(int u){return u==pre[u] ? u:pre[u]=find(pre[u]); } //tarjan_lca算法割路徑 void dfs2(int u,int f){int to;pre[u]=u;dep[u]=dep[f]+1;vis[u]=true;for(int k=head[u];k!=-1;k=edge[k].next){if((to=edge[k].to)!=f){dfs2(to,u);pre[to]=u;}}for(int k=Head[u];k!=-1;k=Lca[k].next){if(!Lca[k].flag&&vis[to=Lca[k].to]){Lca[k].flag=Lca[k^1].flag=true;int flag=0,m=find(to);if(!(k&1)) {flag=1;to^=u^=to^=u;}pathi++;if(to==m){S[pathi]=to;T[pathi]=u;dis[pathi]=dep[u]-dep[to];pret[pathi]=0;Sd[to].push_back(pathi);Tu[u].push_back(pathi);}else if(u==m){S[pathi]=to;T[pathi]=u;dis[pathi]=dep[to]-dep[u];Td[u].push_back(pathi);Su[to].push_back(pathi);}else{lca0[pathi]=m;S[pathi]=to;T[pathi]=m;dis[pathi]=dep[to]-dep[m];Su[to].push_back(pathi);Td[m].push_back(pathi);S[++pathi]=m;T[pathi]=u;dis[pathi]=dep[u]-dep[m];pret[pathi]=dep[to]-dep[m];Sd[m].push_back(pathi);Tu[u].push_back(pathi);}if(flag) u=to;}} }void tarjan_lca(){dfs2(rt,0);/*for(int i=1;i<=pathi;i++){printf("%d %d %d\n",S[i],T[i],dis[i]);}*/ }int cntS[maxm],cntT[maxm],ans[maxn]; //樹上統計 void dfs(int u,int f){int dS=dep[u]+w[u]+maxn,oriS=cntS[dS],dT=dep[u]-w[u]+maxn,oriT=cntT[dT],to;for(unsigned i=0;i<Su[u].size();i++){cntS[dep[S[Su[u][i]]]+maxn]++;}for(unsigned i=0;i<Tu[u].size();i++){cntT[dep[T[Tu[u][i]]]-dis[Tu[u][i]]-pret[Tu[u][i]]+maxn]++;}for(int k=head[u];k!=-1;k=edge[k].next){if((to=edge[k].to)!=f){dfs(to,u);}}ans[u]=cntS[dS]-oriS+cntT[dT]-oriT;for(unsigned i=0;i<Td[u].size();i++){cntS[dep[S[Td[u][i]]]+maxn]--;//if(u==2) cout<<"lca:"<<lca0[Td[u][i]]<<endl;if(lca0[Td[u][i]]==u&&dep[S[Td[u][i]]]+maxn==dS) ans[u]--;}for(unsigned i=0;i<Sd[u].size();i++){cntT[dep[T[Sd[u][i]]]-dis[Sd[u][i]]-pret[Sd[u][i]]+maxn]--;} } //打印答案 void print(){printf("%d",ans[1]);for(int i=2;i<=N;i++) printf(" %d",ans[i]);printf("\n"); }int main(){init();focus();tarjan_lca();dfs(rt,0);print();return 0; }

轉載于:https://www.cnblogs.com/Mychael/p/8282875.html

總結

以上是生活随笔為你收集整理的NOIP2016天天爱跑步 题解报告【lca+树上统计(桶)】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。