CodeForces 593D Happy Tree Party

题目链接: http://codeforces.com/problemset/problem/593/D

---------------------------------------------------------------------------------------------------------------

刚看完题目感觉必须用树链剖分之类的方法，就放弃了，然而我们要发现题目具有如下性质：

一个$ long long $以内的数如果被大于$1$的数除几十次就可以除到$0$了

所以就可以考虑下$LCA$

但如果长度为$1$的边过多复杂度又不靠谱了这时我们又会观察到修改时边的长度只减不增

因此对于长度为$1$的边我们可以进行路径压缩

不过这里的压缩并不是改变原来的树的结构因为改变树的结构就会麻烦许多

我们只需把以长度为$1$的边相连的点放在一个集合内，如果集合内的一个点需要向上查找

就直接找到这个集合的顶端

$（$尽管集合顶端的点并不一定是两点的$LCA $但由于集合内的边长均为$1$ 实际结果是等价的$）$

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int N = 2e5 + ;

 int firste[N], nexte[N << ], v[N << ];

 long long w[N << ];

 int fa[N], d[N], aim[N], fa2[N];

 long long dist[N];

 int n, m, e = ;

 void build_edge(int x, int y, long long z)

 {

     nexte[++e] = firste[x];

     firste[x] = e;

     v[e] = y;

     w[e] = z;

 }

 int findf(int x)

 {

     if(fa2[x] == x)

         return x;

     return fa2[x] = findf(fa2[x]);

 }

 void dfs(int u)

 {

     for(int p = firste[u]; p; p = nexte[p])

         if(!fa[v[p]])

         {

             aim[p / ] = v[p];

             fa[v[p]] = u;

             d[v[p]] = d[u] + ;

             dist[v[p]] = w[p];

             if(w[p] == )

                 fa2[v[p]] = findf(u);

             dfs(v[p]);

         }

 }

 long long check(int x, int y, long long z)

 {

     while(x != y)

     {

         if(d[x] < d[y])

             swap(x, y);

         if(dist[x] == )

             x = findf(x);

         else

         {

             z /= dist[x];

             x = fa[x];

             if(!z)

                 return z;

         }

     }

     return z;

 }

 int main()

 {

     scanf("%d%d", &n, &m);

     int x, y;

     long long z;

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

     {

         scanf("%d%d%lld", &x, &y, &z);

         build_edge(x, y, z);

         build_edge(y, x, z);

     }

     fa[] = ;

     dist[] = ;

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

         fa2[i] = i;

     dfs();

     while(m--)

     {

         scanf("%d", &x);

         if(x & )

         {

             scanf("%d%d%lld", &x, &y, &z);

             printf("%lld\n", check(x, y, z));

         }

         else

         {

             scanf("%d%lld", &x, &z);

             int u = aim[x];

             dist[u] = z;

             if(z == )

                 fa2[u] = findf(fa[u]);

         }

     }

     return ;

 }

巴特西

CodeForces 593D Happy Tree Party

最新文章

热门文章