2599: [IOI2011]Race

分析

　　被memset卡。。。

　　点分治，对于重心，遍历子树，记录一个数组T[i]，表示以重心为起点的长度为i的路径中最少的边数是多少。然后先遍历子树，更新答案，然后在遍历一边更新T，防止出现两个起点在同一棵子树中的情况。

代码

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cctype>
  4 
  5 using namespace std;
  6  
  7 const int N = 200100;
  8 const int INF = 1e9;
  9  
 10 struct Edge{
 11     int to,nxt,w;
 12     Edge() {}
 13     Edge(int a,int b,int c) {to = a,w = b,nxt = c;}
 14 }e[N<<1];
 15 int head[N],siz[N],T[1000010];
 16 bool vis[N];
 17 int n,k,tot,Size,Num,Root,Ans = N;
 18 
 19 inline int read() {
 20     int x = 0,f = 1;char ch=getchar();
 21     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-1;
 22     for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
 23     return x*f;
 24 }
 25 void add_edge(int u,int v,int w) {
 26     e[++tot] = Edge(v,w,head[u]);head[u] = tot;
 27     e[++tot] = Edge(u,w,head[v]);head[v] = tot;
 28 }
 29 void getRoot(int u,int fa) {
 30     siz[u] = 1;
 31     int mx = 0;
 32     for (int i=head[u]; i; i=e[i].nxt) {
 33         int v = e[i].to;
 34         if (v == fa || vis[v]) continue;
 35         getRoot(v,u);
 36         siz[u] += siz[v];
 37         mx = max(siz[v],mx);
 38     }
 39     mx = max(Size-siz[u],mx);
 40     if (mx < Num) Root = u,Num = mx;
 41 }
 42 void dfs1(int u,int fa,int L,int C) {
 43     if (L > k) return ;
 44     Ans = min(Ans,T[k-L]+C);
 45     for (int i=head[u]; i; i=e[i].nxt) {
 46         int v = e[i].to;
 47         if (v == fa || vis[v]) continue;
 48         dfs1(v,u,L+e[i].w,C+1);
 49     }
 50 }
 51 void dfs2(int u,int fa,int L,int C,int f) {
 52     if (L > k) return ;
 53     if (f) T[L] = min(T[L],C);
 54     else T[L] = INF;
 55     for (int i=head[u]; i; i=e[i].nxt) {
 56         int v = e[i].to;
 57         if (v == fa || vis[v]) continue;
 58         dfs2(v,u,L+e[i].w,C+1,f);
 59     }
 60 }
 61 void calcc(int u) {
 62     T[0] = 0;
 63     for (int i=head[u]; i; i=e[i].nxt) {
 64         int v = e[i].to;
 65         if (vis[v]) continue;
 66         dfs1(v,u,e[i].w,1);
 67         dfs2(v,u,e[i].w,1,1);
 68     }
 69     for (int i=head[u]; i; i=e[i].nxt) {
 70         int v = e[i].to;
 71         if (vis[v]) continue;
 72         dfs2(v,u,e[i].w,1,0);
 73     }
 74 }
 75 void solve(int u) {
 76     vis[u] = true;
 77     calcc(u);
 78     for (int i=head[u]; i; i=e[i].nxt) {
 79         int v = e[i].to;
 80         if (vis[v]) continue;
 81         Size = siz[v],Root = 0,Num = 1e9;
 82         getRoot(v,0);
 83         solve(Root);
 84     }
 85 }
 86 int main() {
 87     n = read(),k = read();
 88     for (int i=1; i<=k; ++i) T[i] = INF;
 89     for (int u,v,w,i=1; i<n; ++i) {
 90         u = read(),v = read(),w = read();
 91         add_edge(u+1,v+1,w);
 92         if (w == k) {printf("-1");return 0;}
 93     }
 94     Size = n;Num = 1e9;
 95     getRoot(1,0);
 96     solve(Root);
 97     if (Ans == N) puts("-1");
 98     else printf("%d",Ans);
 99     return 0;
100 }