Cod sursa(job #52832)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 20 aprilie 2007 00:16:05
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;

#define maxn 100010
#define maxx 200010
#define pb push_back
#define maxk 450
#define maxl 31260

int n,m,l,k;
vector <int> a[maxn];
int v[maxx],g[maxn],px[maxn],py[maxn];
int c[maxk],s[maxk][maxl];
short in[maxx];
int b[maxx];
char used[maxn];

void DFS(int nod)
{
     used[nod]=1;
     
     v[++l]=nod;
     px[nod]=l;
     
     for (int i=0;i<g[nod];++i)
       if (!used[a[nod][i]]) DFS(a[nod][i]);
       
     v[++l]=nod;
     py[nod]=l;
}

inline int intro(int x,int y)
{
    return (y>=0) && ((s[x][y/32]&(1<<(y&31)))!=0);
}

inline void mark(int x,int y)
{
     if (!intro(x,y)) s[x][y/32]+=(1<<(y&31));
}

inline void clear(int x,int y)
{
     if (intro(x,y)) s[x][y/32]-=(1<<(y&31));
}

int min(int a,int b)
{
    if (a<b) return a;
    return b;
}

int main()
{
    freopen("arbore.in","r",stdin);
    freopen("arbore.out","w",stdout);
    
    int i,x,y,j,p;
    
    scanf("%d %d ",&n,&m);
    
    for (i=1;i<n;++i)
    {
        scanf("%d %d ",&x,&y);
        a[x].pb(y);
        a[y].pb(x);
    }
    
    for (i=1;i<=n;++i) g[i]=a[i].size();
    
    DFS(1);
    
    k=sqrt(l);
    if (k*k<l/2) k++;
    
    in[1]=1;
    for (i=2;i<=l;++i) 
      if (i>in[i-1]*k) in[i]=in[i-1]+1;
      else in[i]=in[i-1];
      
    for (i=1;i<=in[l];++i) mark(i,0);
      
    for (i=1;i<=m;++i)
    {
        scanf("%d ",&x);
        if (x==1)
        {
            scanf("%d %d",&x,&y);
            
            for (j=in[px[x]]+1;j<in[py[x]];++j) c[j]+=y;
                        
            for (j=px[x];j<=min(k*in[px[x]],py[x]);++j)
            {
                clear(in[px[x]],b[j]);
                b[j]+=y;
            }
            
            for (j=k*(in[px[x]]-1)+1;j<=min(k*in[px[x]],l);++j) mark(in[px[x]],b[j]);
            
            if (k*in[px[x]]<py[x])
            {            
                for (j=k*(in[py[x]]-1)+1;j<=py[x];++j) 
                {
                    clear(in[py[x]],b[j]);
                    b[j]+=y;
                }
                
                for (j=k*(in[py[x]]-1)+1;j<=min(k*in[py[x]],l);++j) mark(in[py[x]],b[j]);
            }                        
        }
        else {
                 scanf("%d ",&x);
                 y=-1;     
                 
/*                 for (j=1;j<=in[l];++j)
                   if (intro(j,x-c[j]))
                   {
                       for (p=(j-1)*k+1;p<=j*k;p++) 
                         if (b[p]+c[j]==x)
                         {
                             y=v[p];
                             break;
                         }
                       break; 
                   }*/
                 
                 printf("%d\n",y);
             }             
    }
    
    return 0;
}