{"id":104,"date":"2010-02-13T01:47:00","date_gmt":"2010-02-12T17:47:00","guid":{"rendered":"http:\/\/localhost\/?p=104"},"modified":"2010-02-13T01:47:00","modified_gmt":"2010-02-12T17:47:00","slug":"sgu_149","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=104","title":{"rendered":"SGU 149"},"content":{"rendered":"

\u6c42\u51fa\u4e00\u68f5\u6811\u4e2d\u79bb\u6bcf\u4e2a\u70b9\u6700\u8fdc\u7684\u70b9\u3002\u3002 \u5178\u578b\u7684\u6811\u5f62DP\u3002\u3002\u8001\u9898\u4e86\u3002\u3002\u770b\u7a0b\u5e8f\u5427\u3002\u3002 Java\u592a\u96be\u5199\u8fd9\u79cd\u9898\u76ee\u4e86\u3002\u3002\u53ea\u597d\u7528c++\u4e86\u3002\u3002
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int> pi;
struct edge
{
int t,c;
edge(int _t,int _c):t(_t),c(_c){}
};
const int maxn=10000;
pi ch[maxn];
int f[maxn];
vector<edge> E[maxn];
typedef vector<edge>::iterator it;
void add_edge(int s,int t,int c)
{
E[s].push_back(edge(t,c));
E[t].push_back(edge(s,c));
}
void Renew(pi&o,int x)
{
if(o.second<x)
{
o.second=x;
if(o.first<o.second)
swap(o.first,o.second);
}
}
void Renew(int&x,int c)
{
x=max(x,c);
}
void dfsch(int x,int fa)
{
ch[x]=pi(0,0);
for(it i=E[x].begin();i!=E[x].end();i++)
if(i->t!=fa)
{
dfsch(i->t,x);
Renew(ch[x],ch[i->t].first+i->c);
}
}
void dfsf(int x,int fa)
{
for(it i=E[x].begin();i!=E[x].end();i++)
if(i->t!=fa)
{
Renew(f[i->t],f[x]+i->c);
if(ch[x].first==ch[i->t].first+i->c)
Renew(f[i->t],ch[x].second+i->c);
else
Renew(f[i->t],ch[x].first+i->c);
dfsf(i->t,x);
}
}
int n;
void init()
{
scanf("%d",&n);
for(int s=1,t,c;s<n;s++)
{
scanf("%d %d",&t,&c);
add_edge(s,t-1,c);
}
}
int main()
{
\/\/freopen("in","r",stdin);
\/\/freopen("out","w",stdout);
init();f[0]=0;
dfsch(0,-1);
dfsf(0,-1);
for(int i=0;i<n;i++)
printf<\/a>("%dn",max(ch[i].first,f[i]));
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u6c42\u51fa\u4e00\u68f5\u6811\u4e2d\u79bb\u6bcf\u4e2a\u70b9\u6700\u8fdc\u7684\u70b9\u3002\u3002 \u5178\u578b\u7684\u6811\u5f62DP\u3002\u3002\u8001\u9898\u4e86\u3002\u3002\u770b\u7a0b\u5e8f\u5427\u3002\u3002 Java\u592a\u96be\u5199\u8fd9\u79cd\u9898\u76ee\u4e86\u3002\u3002\u53ea\u597d\u7528c++\u4e86\u3002\u3002#include<cstdio>#include<vector>#include<utility>#include<algorithm>using namespace std;typedef pair<int,int> pi;struct edge{ int t,c; edge(int _t,int _c):t(_t),c(_c){}};const int maxn=10000;pi ch[maxn];int f[maxn];vector<edge> E[maxn];typedef vector<edge>::iterator it;void add_edge(int s,int t,int c){ E[s].push_back(edge(t,c)); E[t].push_back(edge(s,c));}void Renew(pi&o,int x){ if(o.second<x) { o.second=x; if(o.first<o.second) swap(o.first,o.second); }}void Renew(int&x,int c){ x=max(x,c);}void dfsch(int x,int fa){ ch[x]=pi(0,0); for(it i=E[x].begin();i!=E[x].end();i++) if(i->t!=fa) { dfsch(i->t,x); Renew(ch[x],ch[i->t].first+i->c); }}void dfsf(int x,int fa){ for(it i=E[x].begin();i!=E[x].end();i++) if(i->t!=fa) { […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/104"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=104"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/104\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}