2599: [IOI2011]Race

Time Limit: 70 Sec  Memory Limit: 128 MB

Submit: 3069  Solved: 898

[][][]

Description

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

 

Input

第一行 两个整数 n, k

第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数 表示最小边数量 如果不存在这样的路径 输出-1

Sample Input

4 3

0 1 1

1 2 2

1 3 4

Sample Output

2

---

小总结：

目前遇到的点分治处理有两种：

1.先统计每颗子树，处理一颗子树时使用了之前子树的信息

2.先统计整棵树然后减去同一棵子树里的，可以只一遍邻接链表循环

 

对于本题，

1.可以用d[i]表示之前遍历过的子树中深度为i的最小边数，c[i]表示i到根的边数

然后点分治时，一个个子树遍历，先更新答案在用更新d[]，再一遍遍历把d[]复原（不能用memset，复杂度...）

注意：每次dfsSol里都要d[0]=0,难道有w=0的边？！

2.还可以用那种排序的方法，不过区间min不支持减法，所以记录每种边数出现的次数，就可以减了....

注意：排序往里扫的时候是l<=r，为什么啊？明明同一个点，我太弱了不知道为什么

 

ps：1比2快了10ms

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=2e5+5,K=1e6+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,k,u,v,w;struct edge{    int v,w,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v,int w){    cnt++;    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int size[N],f[N],rt,vis[N],sum;void dfsRt(int u,int fa){    size[u]=1;f[u]=0;    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(vis[v]||v==fa) continue;        dfsRt(v,u);        size[u]+=size[v];        f[u]=max(f[u],size[v]);    }    f[u]=max(f[u],sum-size[u]);    if(f[u]
          
         
        
       
      

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=2e5+5,K=1e6+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,k,u,v,w;struct edge{    int v,w,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v,int w){    cnt++;    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int size[N],f[N],rt,vis[N],sum;void dfsRt(int u,int fa){    size[u]=1;f[u]=0;    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(vis[v]||v==fa) continue;        dfsRt(v,u);        size[u]+=size[v];        f[u]=max(f[u],size[v]);    }    f[u]=max(f[u],sum-size[u]);    if(f[u]
           
            k) r--; int i=r; while(a[l].deep+a[i].deep==k) ans[a[l].c+a[i].c]+=v,i--; l++; }}void dfsSol(int u){ //printf("dfsSol %d\n",u); vis[u]=1; cal(u,0,0,1); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(vis[v]) continue; cal(v,e[i].w,1,-1); sum=size[v]; rt=0;dfsRt(v,0);v=rt; dfsSol(v); }}int main(){ //freopen("in.txt","r",stdin); n=read();k=read(); for(int i=1;i