[POI2014]FarmCraft

题目大意：
　　一个$n(n\le5\times10^5)$个点的树，每个点有一个权值$c_i$，从$1$出发进行欧拉遍历，每个单位时间移动一条边，记每个点$i$被访问到的时间是$t_i$，问最后$\max\{t_i+c_i\}$的最小值（点$1$算作最后访问）。

思路：
　　$f[i]$表示欧拉遍历以$i$为根的子树的时间，$g[i]$表示对于以点$i$为根的子树中，对于每个点$j$，$\max\{t_j+c_j\}-t_i$的最小值。
　　转移时考虑贪心，对于子结点$j$，$g[j]-f[j]$的值可以在遍历别的子树的过程中抵消掉，因此可以将子结点关于$g[j]-f[j]$降序排序并进行转移。最后答案即为$\max(g[1],f[1]+c_1)$。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 int c[N],f[N],g[N];

 std::vector<int> e[N];

 inline void add_edge(const int &u,const int &v) {

     e[u].push_back(v);

     e[v].push_back(u);

 }

 inline bool cmp(const int &a,const int &b) {

     return g[a]-f[a]>g[b]-f[b];

 }

 void dfs(const int &x,const int &par) {

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par) continue;

         dfs(y,x);

         g[y]=std::max(g[y]+,f[y]+=);

     }

     std::sort(e[x].begin(),e[x].end(),cmp);

     g[x]=c[x];

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par) continue;

         g[x]=std::max(g[x],f[x]+g[y]);

         f[x]+=f[y];

     }

 }

 int main() {

     const int n=getint();

     for(register int i=;i<=n;i++) c[i]=getint();

     for(register int i=;i<n;i++) {

         add_edge(getint(),getint());

     }

     dfs(,);

     printf("%d\n",std::max(g[],f[]+c[]));

     return ;

 }

巴特西

[POI2014]FarmCraft

最新文章

热门文章