QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69653#5148. Tree DistancemyeeWA 2075ms168488kbC++114.2kb2022-12-29 15:32:142022-12-29 15:32:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-29 15:32:15]
  • 评测
  • 测评结果:WA
  • 用时:2075ms
  • 内存:168488kb
  • [2022-12-29 15:32:14]
  • 提交

answer

// 那就是希望。
// 即便需要取模,也是光明。

// lxl 题是吧。
// 叫 TEST_164,一看就是机械化大生产的产物。
// 根号做法似乎过不去,考虑 polylog 做法。
// 点分治,算出每个元素的深度,显然即求出区间内最小、次小值之和。
// 这样可以正确统计不同子树的信息,也不会因为子树内部信息干扰答案。
// 问题是这样每个询问都要 O(n\log n),肯定不行。
// 考虑怎么办。
// 怎样的信息可能被考虑?
// 考虑对右端点 r 做扫描线,然后考虑怎样的节点可能被考虑。
// 容易发现,维护一个单调栈,只有每个时刻可能相邻的元素才会被计入答案。
// 把这些信息全部记录下来,不会超过 O(n\log n) 个。
// 直接线段树维护,离线扫描即可。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
std::vector<std::pair<uint,ullt> >Way[200005],D;
bol Gone[200005];
uint getsiz(uint p,uint f){
    uint ans=1;
    for(auto s:Way[p])if(!Gone[s.first]&&s.first!=f)ans+=getsiz(s.first,p);
    return ans;
}
uint getwp(uint p,uint f,uint siz,uint&w,uint&wp){
    uint ans=1,t=0,user;
    for(auto s:Way[p])if(!Gone[s.first]&&s.first!=f)ans+=user=getwp(s.first,p,siz,w,wp),_max(t,user);
    _max(t,siz-ans);if(_min(w,t))wp=p;
    return ans;
}
voi get(uint p,uint f,ullt dep){
    D.push_back({p,dep});
    for(auto s:Way[p])if(!Gone[s.first]&&s.first!=f)get(s.first,p,dep+s.second);
}
std::vector<std::pair<uint,ullt> >Get[200005];
voi dfs(uint p){
    {uint n=getsiz(p,-1);getwp(p,-1,n,n,p);}
    D.clear(),get(p,-1,0),std::sort(D.begin(),D.end());
    std::vector<std::pair<ullt,uint> >Stack;
    for(auto s:D)
    {
        while(Stack.size()&&Stack.back().second>=s.second)
            Get[s.first].push_back({Stack.back().first,Stack.back().second+s.second}),Stack.pop_back();
        if(Stack.size())
            Get[s.first].push_back({Stack.back().first,Stack.back().second+s.second});
        Stack.push_back(s);
    }
    Gone[p]=1;for(auto s:Way[p])if(!Gone[s.first])dfs(s.first);
}
std::vector<uint>Q[200005];
uint L[1000005],R[1000005];
ullt Ans[1000005];
struct Seg{
    Seg*L,*R;uint len;ullt v;
    Seg(uint n):L(NULL),R(NULL),len(n),v(-1llu){if(n>1)L=new Seg(n>>1),R=new Seg(n-(n>>1));}
    voi chg(uint p,ullt w){
        _min(v,w);if(len==1)return;
        p<(len>>1)?L->chg(p,w):R->chg(p-(len>>1),w);
    }
    ullt find(uint l,uint r){
        if(!l&&r==len)return v;
        if(l<(len>>1))
            if(r<=(len>>1))return L->find(l,r);
            else return std::min(L->find(l,len>>1),R->find(0,r-(len>>1)));
        else return R->find(l-(len>>1),r-(len>>1));
    }
};
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint n,q;scanf("%u",&n);
    for(uint i=1,u,v,w;i<n;i++)
        scanf("%u%u%u",&u,&v,&w),
        Way[--u].push_back({--v,w}),
        Way[v].push_back({u,w});
    scanf("%u",&q);
    for(uint i=0;i<q;i++)
        scanf("%u%u",L+i,R+i),L[i]--,Q[R[i]-1].push_back(i);
    dfs(0);
    Seg S(n);
    for(uint i=0;i<n;i++){
        for(auto s:Get[i])S.chg(s.first,s.second);
        for(auto s:Q[i])Ans[s]=S.find(L[s],i+1);
    }
    for(uint i=0;i<q;i++)
        printf("%lld\n",(llt)Ans[i]);
    return 0;
}

// 那就是希望。
// 即便需要取模,也是光明。

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 22556kb

input:

5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5

output:

-1
3
7
7
2

result:

ok 5 number(s): "-1 3 7 7 2"

Test #2:

score: -100
Wrong Answer
time: 2075ms
memory: 168488kb

input:

199999
31581 23211 322548833
176307 196803 690953895
34430 82902 340232856
36716 77480 466375266
7512 88480 197594480
95680 61864 679567992
19572 14126 599247796
188006 110716 817477802
160165 184035 722372640
23173 188594 490365246
54801 56250 304741654
10103 45884 643490340
127469 154479 214399361...

output:

7975953
838538161068
1262
65959
4366
2623368956
158116029
4867978
328055210
4654349801
506443262
339719
76251
76251
4366
138216269
875595
2826267332
2681285
4366
189703
69287
65959
196947420
92126
15146
4072081890
24465023
5718199
189703
92126
1162886184
92195705
92126
189703
76251
189703
4366
-1
-1...

result:

wrong answer 1st numbers differ - expected: '29573323', found: '7975953'